Kirkpatrick–Seidel algorithm

The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with [math]\displaystyle{ \mathcal{O}(n \log h) }[/math] time complexity, where [math]\displaystyle{ n }[/math] is the number of input points and [math]\displaystyle{ h }[/math] is the number of points (non dominated or maximal points, as called in some texts) 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 [math]\displaystyle{ \mathcal{O}(n \log n) }[/math] 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 optimal, it is not very practical for moderate-sized problems.

Algorithm

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 "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.

At the [math]\displaystyle{ i }[/math]th level of the recursion, the algorithm solves at most [math]\displaystyle{ 2^i }[/math] subproblems, each of size at most [math]\displaystyle{ \frac{n}{2^i} }[/math]. The total number of subproblems considered is at most [math]\displaystyle{ h }[/math], since each subproblem finds a new convex hull edge. The worst case occurs when no points can be discarded and the subproblems are as large as possible; that is, when there are exactly [math]\displaystyle{ 2^i }[/math] subproblems in each level of recursion up to level [math]\displaystyle{ \log_2 h }[/math] . For this worst case, there are [math]\displaystyle{ \mathcal{O}(\log h) }[/math] levels of recursion and [math]\displaystyle{ \mathcal{O}(n) }[/math] points considered within each level, so the total running time is [math]\displaystyle{ \mathcal{O}(n \log h) }[/math] as stated.

See also

• Convex hull algorithms