Convex Hulls and Computational Geometry: From Graham Scan to Voronoi Diagrams

Terminology

What & Why

Computational geometry studies algorithms for problems stated in terms of geometric objects: points, lines, polygons, and their relationships. These problems appear everywhere. A GPS system needs to find the nearest gas station (nearest neighbor via Voronoi diagrams). A robotics planner needs to know which obstacles a path might hit (line segment intersection). A game engine needs to build a mesh from a point cloud (Delaunay triangulation). A GIS application needs to compute the boundary of a region from scattered survey points (convex hull).

What makes these problems interesting algorithmically is that naive solutions are often $O(n^2)$ or worse, but clever geometric insight brings them down to $O(n \log n)$. The key primitive underlying nearly every algorithm in this post is the orientation test: given three points, does the path through them turn left, turn right, or go straight? This single test, computed via a cross product, is the building block for convex hulls, intersection detection, and triangulation.

This post covers five core topics:

• Convex hulls: Graham scan ($O(n \log n)$) and Jarvis march ($O(nh)$)
• Line segment intersection: sweep line detection in $O((n + k) \log n)$
• Voronoi diagrams: nearest-neighbor partitions via Fortune's sweep
• Delaunay triangulation: optimal triangulations and their duality with Voronoi diagrams
• Applications: GIS, robotics, mesh generation, collision detection

How It Works

The Orientation Test

Every algorithm in this post relies on a single primitive: given three points $P_1 = (x_1, y_1)$, $P_2 = (x_2, y_2)$, $P_3 = (x_3, y_3)$, determine whether the path $P_1 \to P_2 \to P_3$ turns left, turns right, or is collinear.

Compute the cross product of vectors $\vec{P_1 P_2}$ and $\vec{P_1 P_3}$:

• Positive: counterclockwise (left turn)
• Negative: clockwise (right turn)
• Zero: collinear

Convex Hull: Graham Scan

Graham scan builds the convex hull in $O(n \log n)$ by sorting points by polar angle around the lowest point, then scanning through them while maintaining a stack of hull candidates. At each step, if the new point causes a right turn (clockwise) with the top two stack points, the top is popped. Only left turns survive.

Steps:

1. Find the point with the lowest y-coordinate (break ties by x). Call it the pivot.
2. Sort all other points by polar angle with respect to the pivot.
3. Push the pivot and the first sorted point onto a stack.
4. For each remaining point, while the top two stack points and the new point make a right turn, pop the stack.
5. Push the new point. When done, the stack holds the convex hull vertices in counterclockwise order.

Convex Hull: Jarvis March (Gift Wrapping)

Jarvis march is conceptually simpler. Start from the leftmost point. At each step, find the point that makes the smallest counterclockwise angle from the current direction. This "wraps" around the hull one edge at a time.

The runtime is $O(nh)$ where $h$ is the number of hull vertices. When $h$ is small (e.g., $O(\log n)$), Jarvis march outperforms Graham scan. When most points are on the hull ($h \approx n$), it degrades to $O(n^2)$.

Line Segment Intersection: Sweep Line

Given $n$ line segments, we want to find all $k$ intersection points. A brute-force check of all $\binom{n}{2}$ pairs costs $O(n^2)$. The Bentley-Ottmann sweep line algorithm does it in $O((n + k) \log n)$.

The idea: sweep a vertical line from left to right. Maintain a balanced BST of segments ordered by their y-coordinate at the current sweep position. Events occur at segment endpoints and at intersection points. When two segments become adjacent in the BST, test them for intersection. When they stop being adjacent, no further test is needed.

Event types:

• Left endpoint: insert the segment into the BST, check for intersections with its new neighbors
• Right endpoint: remove the segment from the BST, check if its former neighbors now intersect
• Intersection: swap the two segments in the BST, check for new intersections with their new neighbors

Voronoi Diagrams

Given $n$ sites (points) in the plane, the Voronoi diagram partitions the plane into $n$ regions. Each region $V(p_i)$ contains all points closer to site $p_i$ than to any other site:

The boundaries between regions are segments of perpendicular bisectors between pairs of sites. Voronoi vertices (where three or more regions meet) are equidistant from three or more sites.

Key properties:

• Each Voronoi region is a convex polygon (possibly unbounded)
• The diagram has $O(n)$ vertices, edges, and faces (by Euler's formula)
• The nearest neighbor of any query point $q$ is the site whose Voronoi region contains $q$

Fortune's sweep line algorithm constructs the Voronoi diagram in $O(n \log n)$ time and $O(n)$ space. It sweeps a horizontal line downward, maintaining a "beach line" of parabolic arcs. As the sweep progresses, parabolas grow and their intersections trace out the Voronoi edges.

Delaunay Triangulation

A Delaunay triangulation of a point set $P$ is a triangulation where no point in $P$ lies inside the circumcircle of any triangle. This condition maximizes the minimum angle across all triangles, avoiding long, thin "sliver" triangles that cause numerical problems in simulations.

The Delaunay triangulation is the dual of the Voronoi diagram: connect two sites with an edge if and only if their Voronoi regions share a boundary. This duality means you can compute one from the other in $O(n)$ time.

Key properties:

• Unique for points in general position (no four points on a common circle)
• Contains the nearest-neighbor graph, the minimum spanning tree, and the Gabriel graph as subgraphs
• Maximizes the minimum angle among all possible triangulations
• Has $O(n)$ triangles and edges

Construction approaches:

• Incremental insertion: add points one at a time, re-triangulate locally. Expected $O(n \log n)$ with randomization.
• Divide and conquer: split points, triangulate each half, merge. Worst-case $O(n \log n)$.
• From Voronoi: compute the Voronoi diagram, then take its dual. $O(n \log n)$ via Fortune's algorithm.

Complexity Analysis

Lower Bounds

Convex hull computation has an $\Omega(n \log n)$ lower bound in the algebraic decision tree model. The proof reduces sorting to convex hull: given $n$ numbers $x_1, \ldots, x_n$, map them to points $(x_i, x_i^2)$ on a parabola. The convex hull of these points, read in order, gives the sorted sequence. Since sorting requires $\Omega(n \log n)$ comparisons, so does convex hull.

Voronoi diagrams and Delaunay triangulations share this lower bound by similar reductions.

Implementation

Orientation Test

FUNCTION orient(P1, P2, P3):
    INPUT: three points P1=(x1,y1), P2=(x2,y2), P3=(x3,y3)
    OUTPUT: positive if CCW, negative if CW, zero if collinear

    RETURN (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

Graham Scan

FUNCTION grahamScan(points):
    INPUT: array of n points
    OUTPUT: list of convex hull vertices in CCW order

    // Step 1: find the lowest point (break ties by leftmost)
    pivot ← point with minimum y (then minimum x)
    REMOVE pivot from points

    // Step 2: sort remaining points by polar angle around pivot
    SORT points BY polarAngle(pivot, point) ASCENDING
        // break ties by distance from pivot (closer first)

    // Step 3: scan with a stack
    stack ← [pivot, points[0]]

    FOR i ← 1 TO LENGTH(points) - 1 DO
        WHILE LENGTH(stack) >= 2 AND
              orient(stack[top-1], stack[top], points[i]) <= 0 DO
            POP stack    // right turn or collinear: discard
        END WHILE
        PUSH points[i] onto stack
    END FOR

    RETURN stack

Jarvis March

FUNCTION jarvisMarch(points):
    INPUT: array of n points
    OUTPUT: list of convex hull vertices in CCW order

    hull ← empty list
    start ← leftmost point (minimum x, break ties by minimum y)
    current ← start

    REPEAT
        APPEND current to hull
        candidate ← points[0]

        FOR EACH point IN points DO
            IF point = current THEN CONTINUE
            cross ← orient(current, candidate, point)
            IF candidate = current
               OR cross > 0
               OR (cross = 0 AND dist(current, point) > dist(current, candidate)) THEN
                candidate ← point
            END IF
        END FOR

        current ← candidate
    UNTIL current = start

    RETURN hull

Line Segment Intersection Test

FUNCTION segmentsIntersect(A, B, C, D):
    INPUT: segment AB and segment CD
    OUTPUT: TRUE if they intersect, FALSE otherwise

    d1 ← orient(C, D, A)
    d2 ← orient(C, D, B)
    d3 ← orient(A, B, C)
    d4 ← orient(A, B, D)

    // Standard case: segments straddle each other
    IF d1 * d2 < 0 AND d3 * d4 < 0 THEN
        RETURN TRUE
    END IF

    // Collinear cases: check if endpoints lie on the other segment
    IF d1 = 0 AND onSegment(C, D, A) THEN RETURN TRUE
    IF d2 = 0 AND onSegment(C, D, B) THEN RETURN TRUE
    IF d3 = 0 AND onSegment(A, B, C) THEN RETURN TRUE
    IF d4 = 0 AND onSegment(A, B, D) THEN RETURN TRUE

    RETURN FALSE

FUNCTION onSegment(P, Q, R):
    // Check if R lies on segment PQ (given P, Q, R are collinear)
    RETURN min(P.x, Q.x) <= R.x <= max(P.x, Q.x)
       AND min(P.y, Q.y) <= R.y <= max(P.y, Q.y)

Delaunay: In-Circumcircle Test

FUNCTION inCircumcircle(A, B, C, D):
    INPUT: triangle ABC and query point D
    OUTPUT: TRUE if D lies inside the circumcircle of ABC

    // Points A, B, C must be in CCW order
    // Uses the determinant test:
    //   | Ax-Dx  Ay-Dy  (Ax-Dx)^2+(Ay-Dy)^2 |
    //   | Bx-Dx  By-Dy  (Bx-Dx)^2+(By-Dy)^2 | > 0
    //   | Cx-Dx  Cy-Dy  (Cx-Dx)^2+(Cy-Dy)^2 |

    ax ← A.x - D.x;  ay ← A.y - D.y
    bx ← B.x - D.x;  by ← B.y - D.y
    cx ← C.x - D.x;  cy ← C.y - D.y

    det ← ax * (by * (cx*cx + cy*cy) - cy * (bx*bx + by*by))
         - ay * (bx * (cx*cx + cy*cy) - cx * (bx*bx + by*by))
         + (ax*ax + ay*ay) * (bx * cy - by * cx)

    RETURN det > 0

Real-World Applications

• GIS and mapping: Voronoi diagrams partition territory into service regions (nearest hospital, fire station, cell tower). Convex hulls define the bounding area of geographic features like forest boundaries or city extents.
• Robotics and path planning: the Voronoi diagram of obstacles gives the set of paths that maximize clearance from all obstacles. Convex hulls simplify collision detection by wrapping complex shapes in simpler bounding polygons.
• Mesh generation: Delaunay triangulation produces well-shaped meshes for finite element analysis in engineering simulations. The "no sliver triangles" property ensures numerical stability in heat transfer, fluid dynamics, and structural analysis.
• Computer graphics: terrain rendering from elevation point clouds uses Delaunay triangulation. Convex hulls accelerate ray-object intersection tests in ray tracers.
• Nearest neighbor search: the Voronoi diagram provides $O(\log n)$ nearest-neighbor queries via point location. This is used in k-NN classifiers, spatial databases, and recommendation systems.
• Network design: the Euclidean minimum spanning tree (a subgraph of the Delaunay triangulation) solves problems like connecting cities with minimum total cable length. Computing the Delaunay triangulation first reduces the MST problem from $O(n^2)$ edges to $O(n)$ candidate edges.

Key Takeaways

• The orientation test (a single cross product) is the fundamental primitive of computational geometry, determining left turns, right turns, and collinearity in $O(1)$
• Graham scan computes the convex hull in $O(n \log n)$ using a sort-and-stack approach. Jarvis march runs in $O(nh)$ and is faster when the hull has few vertices.
• The Bentley-Ottmann sweep line finds all $k$ intersections among $n$ segments in $O((n+k) \log n)$, a major improvement over the $O(n^2)$ brute force
• Voronoi diagrams partition the plane by nearest-neighbor ownership and can be built in $O(n \log n)$ via Fortune's sweep. They are dual to Delaunay triangulations.
• Delaunay triangulations maximize the minimum angle, producing high-quality meshes. They contain the MST and nearest-neighbor graph as subgraphs, making them a central structure in computational geometry.