Ultimate convex hull algorithm

The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm" is an algorithm for computing the convex hull of a set of points in the plane, with O(n log h) time complexity, where n is the number of input points and h is the number of points in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the O(n log n) bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel.

Although the algorithm is asymptotically very efficient, it is not very practical for moderate-sized problems.

The basic idea of the algorithm is a kind of reversal of the divide-and-conquer algorithm for convex hulls of Preparata and Hong, dubbed as "marriage-before-conquest" by the authors.

The traditional divide-and-conquer algorithm splits the input points into two equal parts, e.g., by a vertical line, recursively finds convex hulls for the left and right subsets of the input, and then merges the two hulls into one by finding the "bridge edges", bitangents that connect the two hulls from above and below.

The Kirkpatrick–Seidel algorithm splits the input as before, by finding the median of the x-coordinates of the input points. However, the algorithm reverses the order of the subsequent steps: its next step is to find the edges of the convex hull that intersect the vertical line defined by this median x-coordinate, which turns out to require linear time. The points on the left and right sides of the splitting line that cannot contribute to the eventual hull are discarded, and the algorithm proceeds recursively on the remaining points. In more detail, the algorithm performs a separate recursion for the upper and lower parts of the convex hull; in the recursion for the upper hull, the noncontributing points to be discarded are those below the bridge edge vertically, while in the recursion for the lower hull the points above the bridge edge vertically are discarded.

...
Wikipedia