Kirkpatrick–Seidel algorithm
Encyclopedia
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
.
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", bitangent
s 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, while in the recursion for the lower hull the points above the bridge edge are discarded.
At the ith level of the recursion, the algorithm solves at most 2i subproblems, each of size at most n/2i. The total number of subproblems considered is at most h, 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 2i subproblems in each level of recursion up to level log2h. For this worst case, there are O(log h) levels of recursion and O(n) points considered within each level, so the total running time is O(n log h) as stated.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for computing the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of a set of points in the plane, with O(n log h) time complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational 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
Output-sensitive algorithm
In computer science, an output-sensitive algorithm is an algorithm whose running time depends not only on the size of the input but also on the size of the output...
: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm
Gift wrapping algorithm
In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.-Planar case:In the two-dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who published it in 1973; it has O time complexity, where n is the...
, 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
David G. Kirkpatrick
David Galer Kirkpatrick is a professor of computer science at the University of British Columbia. He is known for the Kirkpatrick–Seidel algorithm and his work on Polygon triangulation, and for co-inventing α-shapes and the β-skeleton...
and Raimund Seidel
Raimund Seidel
Raimund G. Seidel is a professor of computer scientist at the Universität des Saarlandes and an expert in computational geometry.Seidel was born in Graz, Austria, and studied with Hermann Maurer at the Graz University of Technology. He received his Ph.D. in 1987 from Cornell University under the...
.
Algorithm
The basic idea of the algorithm is a kind of reversal of the divide-and-conquer algorithm for convex hulls of PreparataFranco P. Preparata
Franco P. Preparata is a computer scientist, the An Wang Professor of Computer Science at Brown University. He is best known for his 1985 computational geometry book with Michael Shamos, for many years the standard textbook in the field, but Preparata has worked in many other areas of computer...
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", bitangent
Bitangent
In mathematics, a bitangent to a curve C is a line L that touches C in two distinct points P and Q and that has the same direction to C at these points...
s that connect the two hulls from above and below.
The Kirkpatrick–Seidel algorithm splits the input as before, by finding the median
Median
In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
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, while in the recursion for the lower hull the points above the bridge edge are discarded.
At the ith level of the recursion, the algorithm solves at most 2i subproblems, each of size at most n/2i. The total number of subproblems considered is at most h, 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 2i subproblems in each level of recursion up to level log2h. For this worst case, there are O(log h) levels of recursion and O(n) points considered within each level, so the total running time is O(n log h) as stated.