Closest Pair & Convex Hull

The gap this subtopic closes

The Math & Geometry Essentials subtopic mentions convex hull by name and moves on ("know that it exists... a full derivation is out of scope"). This subtopic is that derivation, plus its natural companion problem: two classic divide-and-conquer geometry algorithms that show up constantly in graphics, computer vision, and physical simulation, even though they're rare as a primary interview question. Both are worth understanding properly because they're the canonical example of "brute force gives you O(n²); a smarter recursive structure — not a smarter data structure — gets you to O(n log n)," the same divide-and-conquer discipline you built in the Sorting topic, now applied to points instead of numbers.

Closest pair of points

The problem. Given n points in the plane, find the two that are closest together by Euclidean distance.

Brute force: O(n²). Check every pair. This is the correct baseline to state out loud before optimizing — exactly the "brute force as the baseline you optimize from" habit, not a step to skip.

The divide-and-conquer idea: O(n log n).

1. Sort all points by x-coordinate once, up front.
2. Split into left and right halves by a vertical dividing line.
3. Recursively find the closest pair in each half — call the smaller of the two distances d.
4. The subtle part: the true closest pair might straddle the dividing line, one point in each half. Naively checking every left-point against every right-point is back to O(n²). Instead, build a "strip" of only the points within horizontal distance d of the dividing line (any pair farther apart than d in x alone is already worse than what you have) and sort that strip by y-coordinate.
5. The key geometric fact that makes this fast: within the strip, you only ever need to compare each point against the next 6–7 points in y-order. Why: if you divide the strip into d/2 × d/2 boxes, no box can contain more than one point that's part of a closer-than-d pair (any two points in the same d/2 × d/2 box are less than d apart by construction) — so among any point's next few y-sorted neighbors within distance d, at most a small constant number of boxes are in play. This constant-work-per-point claim is why the merge step is O(n) instead of O(n²), and it's the specific insight worth being able to state, not just the conclusion.

A simpler alternative worth knowing: sweep line with a balanced ordered set. Sort by x, sweep left to right maintaining an ordered set (by y-coordinate) of the points within horizontal distance d of the current point, querying only the y ± d range in that set for each new point. Amortized analysis gives the same O(n log n) bound as divide-and-conquer, but the code is a single pass instead of a recursion with a merge step — this is often the version people reach for when solving the problem competitively rather than deriving it from scratch, since it reuses the ordered-set/two-pointer machinery from the Sliding Window and Binary Search topics instead of introducing new divide-and-conquer bookkeeping.

Real-world case study. This exact problem is collision detection in physics engines and games: given hundreds of moving objects each frame, "which two are about to collide" reduces to "which two are closest" (with a radius threshold) — running it as brute force O(n²) is exactly what tanks frame rate as object counts grow, which is why production physics engines (Box2D, Bullet) use spatial partitioning (grids, quadtrees, BVH trees) as a practical stand-in for the same divide-and-conquer locality principle: don't compare far-apart objects at all, restrict comparisons to nearby regions.

Convex hull

The problem. Given n points in the plane, find the smallest convex polygon that contains all of them — imagine stretching a rubber band around every point and letting it snap tight; the points it touches are the hull.

The building block: cross product as a turn direction. For three points O, A, B, the sign of the 2D cross product (A-O) × (B-O) = (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x) tells you the turn direction at O going from A to B: positive means counterclockwise, negative means clockwise, zero means collinear. This is the exact same collinearity test from Math & Geometry Essentials' cheat sheet, repurposed as the core primitive for hull construction — everything below is built on this one O(1) check.

Andrew's monotone chain algorithm — O(n log n). Sort points lexicographically (by x, then y as a tiebreak), then build the lower and upper hulls independently with a simple stack-based scan, and concatenate them:

The mechanism: scanning left to right, maintain a stack of hull candidates; whenever adding the next point would make the last three points turn the wrong way (clockwise, for a lower hull built counterclockwise), the middle point can't be on the hull — pop it. This is a monotonic-stack pattern, structurally the same "discard elements that a new arrival invalidates" idea you built in the Stack topic's monotonic stack subtopic, just with "turn direction" instead of "greater/smaller" as the invalidation test.

Graham scan — the historically-first O(n log n) algorithm, worth knowing by name. Pick the lowest point as a pivot, sort every other point by polar angle around it, then scan with the same cross-product stack logic. It's conceptually similar to monotone chain but needs careful handling of the collinear-angle tie case; monotone chain's plain lexicographic sort has fewer edge cases, which is why it's generally preferred in practice today.

Why O(n log n) is optimal. Any convex hull algorithm can be used to sort a set of numbers (place them on a parabola y = x²; their hull's lower chain, read left to right, is the sorted order) — so the Ω(n log n) comparison-sorting lower bound transfers directly to convex hull. You can't beat this asymptotically with a comparison-based approach, which is worth stating if asked "can we do better?"

Real-world case study. Convex hull underlies object boundary and collision-shape approximation in computer vision and CAD/robotics: a scanned or detected object is a noisy cloud of points, and its convex hull gives a clean, minimal outer boundary — used as a fast, conservative collision proxy (checking hull-vs-hull overlap is far cheaper than checking every point pair) and as a preprocessing step before more expensive exact-shape analysis. It's also the geometric backbone of route/area optimization problems — e.g., finding the minimal enclosing fence or region around a set of locations.

Complexity summary

Algorithm	Brute force	Optimized	Space
Closest pair of points	O(n²)	O(n log n) (divide-and-conquer or sweep line)	O(n)
Convex hull	O(n² ) (naive: test every point against every edge)	O(n log n) (Graham scan / Andrew's monotone chain)	O(n)

Pitfalls and interview gotchas

• Closest pair: re-checking every cross-boundary pair instead of building the strip. The entire point of the algorithm is that the merge step is O(n), not O(n²) — if you're comparing every left point to every right point "just to be safe," you've silently regressed to brute force wearing a divide-and-conquer costume.
• Closest pair: forgetting to re-sort the strip by y before the 6–7-neighbor scan. The points arrive from the x-sorted array; the "only check the next few neighbors" guarantee specifically depends on the strip being y-sorted.
• Convex hull: using < 0 vs <= 0 in the cross-product comparison without knowing which you want. <= 0 builds a strict hull excluding collinear boundary points; < 0 includes points that lie exactly on a hull edge. Problems differ on which they want (e.g., Erect the Fence wants collinear boundary trees included) — check the problem statement, don't default to one blindly.
• Convex hull: forgetting to dedupe input points or handle n <= 2 before the general algorithm. A degenerate all-collinear input, or fewer than 3 points, will break a general-case hull scan that assumes a genuine 2D spread.
• Both: floating-point distance comparisons. Compare squared distances instead of taking a square root when you only need relative ordering — same "avoid floats where an equivalent exact-integer comparison exists" habit from Math & Geometry Essentials.

How to talk about this in an interview

"Brute force checks every pair in O(n²). I can do better by sorting by x and splitting the points in half: recursively solve each half, then handle only the pairs that straddle the dividing line by building a narrow strip around it — sorted by y, each point in the strip only needs to check its next 6-7 y-neighbors, because of a packing argument on d/2-sized boxes. That merge step is O(n), giving O(n log n) overall — the same divide-and-conquer shape as merge sort, just with a geometric argument standing in for the sorted-merge step."

"For convex hull, I'll sort points lexicographically and build the lower and upper chains with a stack, popping any point that makes a non-left turn with the two points before it — that's Andrew's monotone chain, O(n log n), and it's asymptotically optimal because any hull algorithm can be repurposed to sort numbers, so the comparison-sort lower bound applies."