Kirkpatrick-Seidel Algorithm

The Kirkpatrick-Seidel algorithm is an algorithm for computing the convex hull of a set of points in the plane, achieving an output-sensitive time complexity of O(n log h), where n is the number of input points and h is the number of points on the convex hull, so its running time depends on both the input size and the size of the output. Earlier output-sensitive algorithms such as gift wrapping ran in O(nh) time, while non-output-sensitive algorithms typically ran in O(n log n) time, so Kirkpatrick-Seidel offered a significant theoretical improvement. Despite this theoretical optimality, the algorithm is not widely used in practice for moderate-sized data sets because of its implementation complexity and the large constants hidden in its asymptotic bound.