Kirkpatrick–Seidel algorithm

The Kirkpatrick–Seidel algorithm is an algorithm designed for computing the convex hull of a set of points in the plane, offering a time complexity of ${\displaystyle {\mathcal {O}}(n\log h)}$, where ${\displaystyle n}$ is the number of input points and ${\displaystyle h}$ is the number of points on the convex hull. This output-sensitive time complexity implies that the algorithm’s running time depends on both the input size and the size of the output.

Earlier output-sensitive algorithms, such as the gift wrapping algorithm, exhibited asymptotic running times of ${\displaystyle {\mathcal {O}}(nh)}$, while non-output-sensitive algorithms typically ran in ${\displaystyle {\mathcal {O}}(n\log n)}$ time. The Kirkpatrick–Seidel algorithm offers a significant improvement by achieving a more efficient asymptotic bound, making it faster for certain types of input.

Despite its theoretical optimality, the algorithm is not widely used in practice for moderate-sized data sets due to the implementation complexity and constants hidden in the asymptotic notation.