Computational Geometry — Algorithms Course

What you'll learn

Computational geometry brings algorithms to points, lines, and shapes — powering graphics, mapping, robotics, and games. A single primitive, the orientation test, underlies almost everything, including the classic convex hull.

By the end you'll be able to:

Use the cross-product orientation test
Compute a convex hull in O(n log n)
Recognize the sweep-line technique

Points & orientation

The workhorse is the 2-D cross product. For three points O, A, B, the sign of (A−O) × (B−O) tells you whether O→A→B makes a left turn (counter-clockwise, positive), a right turn (clockwise, negative), or is collinear (zero). No trigonometry, no floating point needed — just multiplication and subtraction. Segment intersection, point-in-polygon, and hulls all reduce to these turn tests.

Convex hull

The convex hull is the smallest convex polygon containing every point — imagine a rubber band snapped around them. Andrew's monotone chain sorts the points, then sweeps left-to-right building the lower boundary and right-to-left for the upper, popping any point that would cause a non-left turn. It's O(n log n), dominated by the sort:

Convex hull of a point set

The green polygon is the hull; gray points lie strictly inside.

In code

Language

convex_hull.py

def cross(o, a, b):
    # >0 left turn (CCW), <0 right turn (CW), 0 collinear
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

def convex_hull(points):
    pts = sorted(set(points))            # by x, then y
    if len(pts) <= 2:
        return pts
    def half(seq):
        h = []
        for p in seq:
            while len(h) >= 2 and cross(h[-2], h[-1], p) <= 0:
                h.pop()                  # pop non-left turns
            h.append(p)
        return h
    lower = half(pts)
    upper = half(reversed(pts))
    return lower[:-1] + upper[:-1]       # drop shared endpoints

Note

Graham scan is the other classic hull algorithm: sort points by angle around the lowest point, then walk them, popping right turns. Same O(n log n). Both keep only the points that turn consistently one way.

The sweep line

Many geometry problems yield to a sweep line: imagine a vertical line moving across the plane, processing events (a segment starts, ends, or crosses another) in x-order and keeping an ordered set of "active" objects. It finds all k segment intersections in O((n + k) log n), and — a callback to Module 12 — the closest pair of points can be solved this way too, as an alternative to divide and conquer.

Key idea

Two ideas carry most of computational geometry: the orientation test for local turn decisions, and the sweep line for processing events in order. Master both and a surprising number of geometry problems fall.

Recap & quick check

Key takeaways

The cross-product sign classifies three points as a left turn, right turn, or collinear.
Orientation tests need no trig or floats — just integer multiply and subtract.
The convex hull is the smallest convex polygon enclosing all points.
Monotone chain (and Graham scan) compute it in O(n log n).
The sweep line processes geometric events in x-order for intersections and closest pair.

Quick check

1. What does the sign of the 2-D cross product (A−O)×(B−O) tell you?

2. What is a convex hull?

3. Andrew's monotone chain runs in:

4. The sweep-line technique processes events in order of:

We've solved a lot. Now: which problems can we never solve quickly? Next up: Module 35 — Intractability: P, NP & NP-Completeness.