Kirkpatrick-Seidel Algorithm

Purpose: The “ultimate convex hull algorithm” (1986) — computes a 2D convex hull in $O(n\log h)$, output-sensitive and optimal. It predates Chan’s algorithm by a decade but is considerably harder to implement.

The Idea: marriage before conquest

Ordinary divide and conquer splits the input, recurses, then merges — and the merge is where hull algorithms lose time. Kirkpatrick and Seidel invert the order: do the “merge” first, so that the recursion only ever works on points that are actually going to contribute.

Building the upper hull of a point set:

1. Find the median $x$-coordinate in $O(n)$ (median of medians).
2. Find the bridge — the single upper-hull edge that crosses the vertical line at the median. This is done in $O(n)$ using a clever pairing-and-pruning argument (essentially a 2D linear program solved by prune-and-search).
3. The bridge’s endpoints are guaranteed hull vertices. Discard every point lying below the bridge — they cannot be on the hull.
4. Recurse on the surviving points to the left and to the right.

Because step 3 throws away non-hull points before recursing, the recursion tree has only $O(h)$ leaves.

Complexity

$T(n,h)=O(n)+T(n_1,h_1)+T(n_2,h_2),h_1+h_2=h-2$

which solves to $O(n\log h)$. This is optimal: there is a matching $\Omega (n\log h)$ lower bound in the algebraic decision tree model.

• Time: $O(n\log h)$
• Space: $O(n)$

Kirkpatrick-Seidel vs Chan

	Kirkpatrick-Seidel	Chan
Time	$O(n\log h)$	$O(n\log h)$
Technique	prune-and-search, bridge finding	grouping + doubling guess
Needs	median finding, 2D LP	Graham scan + binary search
Implementation	hard	moderate
Extends to 3D	awkwardly	naturally

Chan’s algorithm achieves the same optimal bound with dramatically simpler ingredients, which is why it is the one people learn. Kirkpatrick-Seidel’s lasting contribution is the prune-and-search paradigm itself.

Prune-and-search elsewhere

The pattern — spend linear time discarding a constant fraction of the input, then recurse — is the engine behind several optimal algorithms:

• Median of medians selection in $O(n)$
• Megiddo’s linear-time LP in fixed dimension (and its randomized simplification, Seidel’s LP algorithm)
• Welzl’s minimum enclosing circle in expected $O(n)$
• Slope selection and ham-sandwich cuts

When a geometry problem has a linear-time algorithm despite “obviously” needing a sort, prune-and-search is usually why.

Variants / Use Cases

• Convex Hull — the topic page and what to actually write
• Chan’s algorithm — the implementable optimal alternative
• Welzl — prune-and-search for the smallest enclosing circle
• Seidel’s LP — randomized linear programming in low dimension