What Is Computational Geometry? Algorithms That Reason About Space

Somewhere between your GPS calculating a route and a physics engine detecting whether two hitboxes are touching, an algorithm is doing arithmetic on coordinates. You never see it. You never asked for it. And then one day an interviewer asks you to implement it from scratch.

Computational geometry is the study of algorithms on geometric objects: points, lines, segments, polygons. It shows up in interviews less often than graph traversal or dynamic programming. When it does, candidates who understand the underlying primitives sail through while everyone else invents increasingly creative wrong answers.

What Does Computational Geometry Actually Solve?

• Given a set of points, find the smallest convex polygon containing all of them (convex hull).
• Given n points in a plane, find the two that are closest together (closest pair).
• Given a set of line segments, do any two of them intersect?
• Given a polygon and a query point, is the point inside?
• Given n points, partition the plane so each region contains the points closest to one center (Voronoi diagram).

Each has an obvious brute-force solution that is O(n²) or worse. Each has a clever algorithm that gets to O(n log n). The gap between those two is where the whole field lives.

Every geometric problem starts here. The O(n log n) algorithms are literally the plot of this post.

The Primitive Behind Everything: Six Multiplications and a Sign

Before any major algorithm, you need one building block: the orientation test.

Given three points A, B, C, the test answers: are they arranged counterclockwise, clockwise, or collinear?

def orientation(A, B, C):
    cross = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
    if cross > 0:
        return 1
    elif cross < 0:
        return -1
    else:
        return 0

This is the cross product of vectors AB and AC, and its sign tells you everything. Positive means left turn (counterclockwise), negative means right turn (clockwise), zero means the three points are collinear.

Time: O(1). Space: O(1). Six arithmetic operations.

That's it. Every major computational geometry algorithm bottoms out on some form of this test. Convex hull, segment intersection, point-in-polygon. They all reduce to asking "which way is this turn?" You commit these six multiplications to memory and a surprising number of hard problems fold open.

Me explaining why the cross product sign determines convex hull membership.

Convex Hull: The One Geometry Algorithm Interviews Actually Ask

The convex hull of a point set is the smallest convex polygon containing all the points. The classic mental image: press a rubber band around all the points and release it. The shape it snaps to is the convex hull.

This appears directly on LeetCode as problem 587 ("Erect the Fence"). Yes, that is the real name.

Graham Scan is the standard interview algorithm. Sort the points by polar angle from the lowest point, then sweep through them maintaining a stack. At each new point, pop any stack entry that would create a clockwise turn.

from functools import cmp_to_key

def convex_hull(points):
    pivot = min(points, key=lambda p: (p[1], p[0]))
    
    def compare(a, b):
        cross = (
            (a[0] - pivot[0]) * (b[1] - pivot[1]) -
            (a[1] - pivot[1]) * (b[0] - pivot[0])
        )
        if cross > 0:
            return -1
        elif cross < 0:
            return 1
        da = (a[0] - pivot[0])**2 + (a[1] - pivot[1])**2
        db = (b[0] - pivot[0])**2 + (b[1] - pivot[1])**2
        return -1 if da < db else 1
    
    sorted_pts = sorted(points, key=cmp_to_key(compare))
    
    hull = []
    for pt in sorted_pts:
        while len(hull) >= 2 and orientation(hull[-2], hull[-1], pt) <= 0:
            hull.pop()
        hull.append(pt)
    
    return hull

Time: O(n log n), dominated by the sort. The sweep itself is O(n) because each point is pushed and popped at most once. Space: O(n) for the hull.

The pop condition is where the orientation test earns its keep. If the last three points make a clockwise turn (or are collinear), the middle one cannot be on the convex hull and gets evicted. The whole algorithm is just that rule, applied repeatedly.

Closest Pair: The Strip Check That Looks Catastrophic

Given n points, find the two that are closest. Brute force checks all n(n-1)/2 pairs in O(n²). The divide-and-conquer approach achieves O(n log n) through a non-obvious geometric argument.

Sort by x-coordinate. Split the points in half. Recurse on each half to get the minimum distance d within each side. Then check the "strip" of points within distance d of the dividing line, because the true closest pair might straddle the boundary.

import math

def closest_pair_distance(points):
    pts = sorted(points, key=lambda p: p[0])
    return _closest(pts)

def _closest(pts):
    n = len(pts)
    if n <= 3:
        min_d = float('inf')
        for i in range(n):
            for j in range(i + 1, n):
                min_d = min(min_d, math.dist(pts[i], pts[j]))
        return min_d
    
    mid = n // 2
    mid_x = pts[mid][0]
    d = min(_closest(pts[:mid]), _closest(pts[mid:]))
    
    strip = [p for p in pts if abs(p[0] - mid_x) < d]
    strip.sort(key=lambda p: p[1])
    
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and strip[j][1] - strip[i][1] < d:
            d = min(d, math.dist(strip[i], strip[j]))
            j += 1
    
    return d

The strip loop looks like a trap. The inner while loop appears to run O(n) times, giving O(n²) overall. It doesn't. By a packing argument, any d × 2d rectangle in the strip contains at most 8 points, because any two points within one half are already at least distance d apart. The inner while runs at most 7 times per outer iteration. Strip check is O(n).

The recurrence T(n) = 2T(n/2) + O(n log n) solves to O(n log²n), dropping to O(n log n) with a presorted-y trick.

The Sweepline: One Pattern, Every Problem

Imagine dragging a vertical line left-to-right across a diagram. Process events (segment endpoints, intersections) in sorted x-order, maintaining a data structure of "active" segments at the current x position. That's the sweepline.

It solves:

• Any-segment intersection in O(n log n) instead of O(n²)
• The skyline problem (LeetCode 218): O(n log n) with a max-heap
• Area of union of rectangles: O(n log n) with a segment tree on the y-axis
• Calendar conflict detection: same pattern, different objects

The complexity is always the same. Sorting events is O(n log n). Processing each event with a balanced BST or heap is O(log n). Total events is O(n). The whole thing is O(n log n). Once you see the pattern once, every sweepline problem feels like a costume party where you already know everyone.

Point in Polygon: Oddly Satisfying

Given a polygon and a query point, determine whether the point is inside.

Ray casting is the standard approach. Shoot a ray from the query point rightward and count how many polygon edges it crosses. Odd count means inside, even means outside.

def point_in_polygon(point, polygon):
    x, y = point
    n = len(polygon)
    inside = False
    j = n - 1
    for i in range(n):
        xi, yi = polygon[i]
        xj, yj = polygon[j]
        if (yi > y) != (yj > y):
            if x < (xj - xi) * (y - yi) / (yj - yi) + xi:
                inside = not inside
        j = i
    return inside

Time: O(n). Space: O(1). The condition checks whether the ray crosses each edge, handling horizontal-edge and vertex-touching cases implicitly.

The Complexity Table You Should Memorize

Problem	Brute Force	Optimal
Convex hull	O(n²)	O(n log n)
Closest pair	O(n²)	O(n log n)
Segment intersection (any)	O(n²)	O(n log n)
Point in polygon	O(n)	O(log n) with preprocessing
k nearest neighbors	O(kn)	O(k log n) with k-d tree

The O(n log n) wall is not accidental. For many geometric problems you can prove an Ω(n log n) lower bound by reducing comparison sorting to the geometric problem. Sweepline and divide-and-conquer algorithms that hit this bound are provably optimal.

This connects directly to the comparison sort lower bound: geometric algorithms and sorting share the same information-theoretic floor.

Why You Should Care Even if Your Company Never Asks Geometry

Most computational geometry doesn't show up at most companies. Three things make it worth understanding anyway.

The orientation test appears in disguise. LeetCode 149 ("Max Points on a Line") requires detecting collinear points. The "check if a rectangle is valid" class of problems reduces to cross products. Any problem asking whether a path turns left or right is an orientation test. You've been doing geometry problems. You just didn't know it.

The sweepline pattern recurs. The skyline problem, interval union problems, and calendar conflict detection all use the same structure. Understanding one makes the others obvious. See how divide and conquer underlies the same log factor in merge sort and closest pair.

The convex hull is a direct interview problem. Some companies ask it. "Erect the Fence" on LeetCode is rated Hard and requires a working Graham Scan implementation. Knowing the algorithm cold means you can focus on explaining the invariant rather than deriving it under pressure.

If you want to practice talking through why the hull pop condition works, or why the strip check doesn't blow up to O(n²), SpaceComplexity runs voice-based mock interviews where you explain your reasoning out loud. That's the hard part of geometry problems: the geometric argument, not the loop.

The Short List

• Orientation test: Memorize the cross product formula. Positive = CCW, negative = CW, zero = collinear.
• Convex hull: Understand Graham Scan conceptually. Know why it is O(n log n) and why each point is popped at most once.
• Cross product for collinearity: Directly used in "Max Points on a Line" and similar problems.
• Sweepline concept: Know the event-queue + active-set pattern. Recognize when a problem is sweepline-shaped.
• Ray casting: Point-in-polygon is O(n) and occasionally appears in grid problems.

Further Reading

• Computational Geometry Algorithms and Applications (de Berg et al.): the standard graduate textbook, freely available online
• Convex Hull Algorithms on Wikipedia: formal descriptions and complexity proofs for Graham Scan, Jarvis March, and others
• CP-Algorithms: Geometry: competitive programming reference with clean implementations of the orientation test, convex hull, and sweepline
• GeeksforGeeks: Geometric Algorithms: survey of the main algorithms with worked examples
• LeetCode 587: Erect the Fence: the canonical interview problem that requires a working convex hull implementation