Computational geometry

1 · Why this matters

Computational geometry is the corner of LeetCode you can mostly skip until you can't. Product interviews almost never ask it. Graphics, robotics, GIS, EDA, and competitive programming ask nothing else. The problems are mechanically straightforward once you know the primitives but unsolvable without them.

• LC 587 — Erect the Fence. Convex hull of a point set. The textbook problem.
• LC 218 — The Skyline Problem. Sweep line over building events. A senior-onsite favourite.
• LC 149 — Max Points on a Line. Slope normalisation by GCD. Looks geometric, is really a hash-map problem with care.
• LC 939 — Minimum Area Rectangle. Brute over pairs as diagonals, hash-set lookups.
• LC 1232 — Check If It Is a Straight Line. Single orientation check.
• LC 1453 — Maximum Number of Darts Inside Circle. Disk-cover via pair-induced circles.

The recognition heuristic: "set of 2D points" plus "find a geometric property" (area, hull, intersection, distance, containment). Reach for the primitive first.

2 · The orientation predicate

Given three points p, q, r, the cross product (q - p) × (r - p) tells you which way the turn at q goes:

• > 0 — counter-clockwise turn (r is to the left of p → q).
• < 0 — clockwise turn (r is to the right).
• = 0 — collinear (p, q, r on one line).

In Go, with integer coordinates (the safe default — keeps you out of float-precision hell):

type P struct{ x, y int }

// cross returns (q - p) x (r - p).
//   > 0  -> CCW turn at q
//   < 0  -> CW turn at q
//   = 0  -> collinear
// Use int64 if coordinates can be up to ~10^5 — products fit in 60 bits.
func cross(p, q, r P) int {
    return (q.x-p.x)*(r.y-p.y) - (q.y-p.y)*(r.x-p.x)
}

3 · Convex hull — Andrew's monotone chain

Algorithm. Sort points by (x, y). Build the lower hull left-to-right: for each point, pop the last hull point while the turn would be non-left (cross ≤ 0). Build the upper hull the same way right-to-left. Concatenate, drop the duplicated endpoints. O(n log n) for the sort, O(n) for the chain construction.

Why "monotone chain": the lower hull is a sequence of points whose x coordinates are monotonically increasing. So is the upper. Their concatenation is the closed hull. Cleaner to implement than Graham scan (no polar-angle sort, no special start point).

// Andrew's monotone chain convex hull. O(n log n).
// Returns hull points in CCW order, no duplicate endpoint.
// Set strict=true to drop collinear hull points (use < instead of <=).
import "sort"

func convexHull(pts []P, strict bool) []P {
    n := len(pts)
    if n <= 1 {
        return append([]P(nil), pts...)
    }
    // Sort by x, then y
    p := append([]P(nil), pts...)
    sort.Slice(p, func(i, j int) bool {
        if p[i].x != p[j].x {
            return p[i].x < p[j].x
        }
        return p[i].y < p[j].y
    })

    keep := func(c int) bool {
        if strict {
            return c > 0
        }
        return c >= 0
    }

    hull := make([]P, 0, 2*n)

    // Lower hull
    for _, pt := range p {
        for len(hull) >= 2 && !keep(cross(hull[len(hull)-2], hull[len(hull)-1], pt)) {
            hull = hull[:len(hull)-1]
        }
        hull = append(hull, pt)
    }

    // Upper hull
    lo := len(hull) + 1
    for i := n - 2; i >= 0; i-- {
        pt := p[i]
        for len(hull) >= lo && !keep(cross(hull[len(hull)-2], hull[len(hull)-1], pt)) {
            hull = hull[:len(hull)-1]
        }
        hull = append(hull, pt)
    }
    return hull[:len(hull)-1]   // drop duplicated first point
}

4 · Convex hull — Graham scan

Older but worth knowing. Pick the bottom-most point (lowest y, then leftmost x) — it's guaranteed to be on the hull. Sort the others by polar angle relative to it. Scan in order; pop the stack while the next point would make a non-left turn.

Same O(n log n) complexity. Monotone chain wins on three fronts:

• Sort key is simpler. Lexicographic (x, y), not polar angle (which involves cross products in the comparator).
• No special start point. Graham needs the bottom-most; monotone chain doesn't care.
• Numerically more stable. Polar-angle comparators can flip sign on near-collinear points.

Graham is still the version most textbooks describe. If you remember only one, remember monotone chain.

5 · Sweep line — LC 218 The Skyline Problem

Problem. Given a set of buildings as (left, right, height) triples, return the skyline as a list of (x, y) key-points. A key-point is a position where the outline changes height.

Sweep-line shape. Convert each building into two events: a "+" at left and a "−" at right. Sort events by x; process them in order. Maintain a multiset of active building heights. After each event, the current skyline height is the max of the active set. When that max changes between events, emit a key-point at the event's x.

// LC 218 — The Skyline Problem. O(n log n) via a max-heap with lazy deletion.
import (
    "container/heap"
    "sort"
)

type item struct{ h, end int }   // h = height, end = right edge (for lazy deletion)
type maxHeap []item

func (h maxHeap) Len() int            { return len(h) }
func (h maxHeap) Less(i, j int) bool  { return h[i].h > h[j].h }
func (h maxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *maxHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func getSkyline(buildings [][]int) [][]int {
    // Build event list — one entry per critical x
    xs := map[int]bool{}
    for _, b := range buildings {
        xs[b[0]] = true
        xs[b[1]] = true
    }
    xList := make([]int, 0, len(xs))
    for x := range xs {
        xList = append(xList, x)
    }
    sort.Ints(xList)

    // Index buildings by their left edge for fast push at each event
    sort.Slice(buildings, func(i, j int) bool { return buildings[i][0] < buildings[j][0] })

    h := &maxHeap{item{0, 1<<30}}  // ground level — always active
    heap.Init(h)
    bi := 0
    prevH := 0
    var out [][]int

    for _, x := range xList {
        // Push all buildings starting at or before x
        for bi < len(buildings) && buildings[bi][0] <= x {
            heap.Push(h, item{buildings[bi][2], buildings[bi][1]})
            bi++
        }
        // Lazy-pop any expired buildings (whose right edge is <= x)
        for (*h)[0].end <= x {
            heap.Pop(h)
        }
        curH := (*h)[0].h
        if curH != prevH {
            out = append(out, []int{x, curH})
            prevH = curH
        }
    }
    return out
}

6 · Line segment intersection

Given segments (p1, p2) and (p3, p4), do they intersect? Use the orientation predicate on the four triples. Four orientations:

• o1 = orient(p1, p2, p3)
• o2 = orient(p1, p2, p4)
• o3 = orient(p3, p4, p1)
• o4 = orient(p3, p4, p2)

Proper intersection: sign(o1) ≠ sign(o2) AND sign(o3) ≠ sign(o4). Each segment straddles the line through the other.

Collinear/touching cases (one or more orientation is zero): check whether the zero-oriented point lies on the segment (coordinate bounding-box test). T-junctions and shared endpoints land here.

func sign(x int) int {
    if x > 0 { return 1 }
    if x < 0 { return -1 }
    return 0
}

// onSegment: assumes p, q, r are collinear; returns true if q lies on segment pr.
func onSegment(p, q, r P) bool {
    return min2(p.x, r.x) <= q.x && q.x <= max2(p.x, r.x) &&
        min2(p.y, r.y) <= q.y && q.y <= max2(p.y, r.y)
}

func segmentsIntersect(p1, p2, p3, p4 P) bool {
    o1 := sign(cross(p1, p2, p3))
    o2 := sign(cross(p1, p2, p4))
    o3 := sign(cross(p3, p4, p1))
    o4 := sign(cross(p3, p4, p2))

    // General (proper) case
    if o1 != o2 && o3 != o4 {
        return true
    }
    // Special cases — collinear and a point lies on the other segment
    if o1 == 0 && onSegment(p1, p3, p2) { return true }
    if o2 == 0 && onSegment(p1, p4, p2) { return true }
    if o3 == 0 && onSegment(p3, p1, p4) { return true }
    if o4 == 0 && onSegment(p3, p2, p4) { return true }
    return false
}

7 · Point in polygon

Two standard algorithms. Both work on simple polygons (no self-intersection); behaviour on the boundary needs explicit handling.

Ray casting

Cast a horizontal ray from the test point to the right. Count how many polygon edges it crosses. Odd → inside, even → outside. O(n).

Two edge cases worth knowing about:

• Ray passes through a vertex. If you don't handle it, you may count one edge twice or zero times. Standard fix: count an edge only if the ray's y is strictly between the edge's endpoints' y's (half-open at the top).
• Ray runs along an edge. The horizontal-ray-with-horizontal-edge degeneracy. Skip horizontal edges in the crossing count and handle them separately if you need boundary classification.

Winding number

Sum the signed angle each edge subtends at the test point. The total is 2π·k for some integer k (the winding number); k ≠ 0 means inside. More robust against degenerate cases but needs atan2 (or an integer-only version with cross-product orientation, which is what competitive programmers usually implement).

8 · Closest pair of points

Given n points, find the pair with minimum Euclidean distance. Brute force is O(n²); divide-and-conquer gets you O(n log n).

1. Sort by x once (and keep a separate y-sorted view).
2. Divide at the median x. Recurse on both halves; get the minimum distance d from the two recursions.
3. Conquer the strip. Any closer pair that straddles the median lies within distance d of the median line. Collect those points (in y-sorted order), and for each, compare against at most the next 7 (a geometric bound).

Strictly O(n log n) with the y-sorted-strip trick. The naive recursion without the strip optimisation degrades to O(n log² n) — still fast in practice, simpler to write.

Almost no LeetCode problem actually requires the divide-and-conquer version (LC 973 K Closest Points to Origin is O(n log k) via heap; closest-pair appears in some Google interview problems and in KD-tree-style nearest-neighbour questions).

9 · Worked medium — LC 149 Max Points on a Line

Problem. Given n 2D points, return the maximum number that lie on a single straight line. n ≤ 300, coordinates int.

Approach. For each anchor point, hash every other point's slope relative to the anchor; the most common slope is the max-on-line through that anchor. O(n²) over anchors, O(n) per anchor.

The catch. "Slope" as a float introduces precision bugs (1/3 and 2/6 should be equal, often aren't in IEEE 754). Use the reduced fraction (dy / g, dx / g) with g = gcd(|dy|, |dx|) and sign-normalised so vertical and negative slopes hash consistently.

// LC 149 — Max Points on a Line. O(n^2) time, O(n) extra per anchor.
func gcd(a, b int) int {
    if a < 0 { a = -a }
    if b < 0 { b = -b }
    for b != 0 { a, b = b, a%b }
    return a
}

func maxPoints(points [][]int) int {
    n := len(points)
    if n <= 2 {
        return n
    }
    best := 0
    for i := 0; i < n; i++ {
        slopes := map[[2]int]int{}
        duplicates := 1   // count of points identical to anchor i (including anchor itself)
        localBest := 0
        for j := 0; j < n; j++ {
            if j == i {
                continue
            }
            dx := points[j][0] - points[i][0]
            dy := points[j][1] - points[i][1]
            if dx == 0 && dy == 0 {
                duplicates++
                continue
            }
            g := gcd(dx, dy)
            dx /= g
            dy /= g
            // Sign-normalise: force dx >= 0, and if dx == 0 force dy > 0
            if dx < 0 || (dx == 0 && dy < 0) {
                dx, dy = -dx, -dy
            }
            key := [2]int{dx, dy}
            slopes[key]++
            if slopes[key] > localBest {
                localBest = slopes[key]
            }
        }
        if localBest+duplicates > best {
            best = localBest + duplicates
        }
    }
    return best
}

10 · Worked hard — LC 218 walkthrough

Re-tracing the skyline sweep from Section 5 with a concrete input. Three buildings: [2, 9, 10], [3, 7, 15], [5, 12, 12].

Output: [[2,10], [3,15], [7,12], [12,0]]. The * entries in "active heights" mark expired entries that the lazy-pop will clean up the next time they sit at the heap top.

11 · Sister algorithms

• Bentley-Ottmann — sweep-line for finding all intersections among n line segments in O((n + k) log n), where k is the number of intersections. The classical algorithm; rarely asked but the canonical reference for "sweep line over segments".
• KD-tree — partition tree for nearest-neighbour and range queries on 2D points. O(log n) average for nearest neighbour. The data structure behind most "spatial index" interview questions.
• Rotating calipers — given a convex polygon, find its diameter (farthest pair of vertices) or the width or all antipodal pairs in O(n). Built on top of the convex hull.
• Half-plane intersection — intersect n half-planes in O(n log n). Returns the feasible region of a 2D linear program.
• Voronoi / Delaunay — the dual structures for "which seed point is closest" queries. Beyond LeetCode but central in computational-geometry textbooks.

12 · How to solve a hard geometry problem step-by-step

1. Reach for the primitive. Almost every geometry problem reduces to cross products, dot products, or distances. Before reaching for an algorithm, name the predicate you need: "do these three points turn left", "is this point inside this convex polygon", "do these segments intersect".
2. Decide on coordinates. Are inputs integer or real? Integer → use int64 cross products, no epsilon. Real → use floats but think about scale (coordinate compression can save you).
3. Sort by the right key. Sweep line wants x. Convex hull wants (x, y) lexicographic. Polar-sort wants atan2 (avoid if possible). The sort key is half the algorithm.
4. Sweep events. If the problem has "n intervals" or "n rectangles" or "n line segments" with overlap, model each as start/end events on the x-axis and process in order with an active set.
5. Beware degeneracies. Collinear points, vertical lines, identical points, ties in the sort key — geometry algorithms famously break on these. Add a unit test with three collinear points and one with a vertical line before submitting.

13 · Floating point and integer pitfalls

• Integer overflow on cross products. If coordinates fit in int32 (up to ~2·10⁹) the cross product can overflow — products of two int32 values can need 62 bits. Always cast to int64 for cross products when coordinates exceed 10⁴.
• Float epsilon comparisons. a == b almost never works for floats. Use |a - b| < eps with an eps appropriate to the scale (1e-9 for unit-square inputs, larger for big-coordinate problems).
• Polar angle ties. atan2(y, x) returns the same value for points at the same angle but different distances. If you need to break ties by distance, do it explicitly in the comparator.
• Mixing strict and non-strict orientation. Convex hull with cross < 0 vs cross ≤ 0 changes whether collinear hull points are kept. Both are correct for different problems; choose deliberately.
• GCD with sign. gcd(-2, 4) may give 2 or -2 depending on the implementation. Take absolute values before computing GCD if you're using the result as a normaliser.
• Slope of vertical lines. dx == 0 means infinite slope. If you're using floats it's NaN/Inf; if integers, divide-by-zero. Always special-case vertical lines.

14 · Further reading

• CP-Algorithms — Geometry chapter. The free web reference. Andrew's hull, sweep line, point in polygon, convex hull trick all present. cp-algorithms.com/geometry.
• de Berg, Cheong, van Kreveld, Overmars — Computational Geometry: Algorithms and Applications (3rd ed). The textbook. Every named algorithm in this article has a chapter; the proofs are the value, not the pseudocode.
• O'Rourke — Computational Geometry in C (2nd ed). Older, more code-focused. The integer-arithmetic emphasis is unusual in textbooks and matches competitive-programming practice.
• Tony Wang / Algorithms Live — geometry videos. The clearest free walkthroughs of convex hull and sweep line. Search for "Algorithms Live convex hull" on YouTube.
• Codeforces blog — "Geometry concepts" by Petr. The competitive-programming-focused tour; the cross-product-first framing on this page comes from there.
• Adjacent: monotonic stack. Andrew's monotone chain is a monotonic-stack algorithm in disguise — the "pop while turn isn't left" rule is exactly the monotone-stack invariant.
• Adjacent: heap. The skyline problem is a heap problem dressed up as geometry. The geometry is just the event model.