Kirkpatrick–Seidel algorithm

The Kirkpatrick-Seidel algorithm, called the ultimate convex hull algorithm is the first output-sensitive algorithm of computing of the convex hull of the 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.

Algoritm

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 would require splitting the input points into two equal parts, e.g., by a vertical line, recursively finding convex hulls for the left and right pointsets, and then merging the two hulls into one by finding the "bridge edges", tangential to the two hulls from above and below.

The "ultimate" algorithm first finds the median of the x-coordinates of the input pointset. Then the algorithm finds the edges of the convex hull that intersect the vertical line with this median x-coordinate (and the corresponding vertices on the conex hull), which turns out to require the linear time. After that the input points are split into the left and right halves, in linear time.

Since at each level of recursion new output points are found, the depth of recursion is logarithmic on the number of the output points, hence the staed tiome complexity.

See also

• Chan's algorithm, a simpler out-put-sensitive convex hull algorithm.