Reading time: 15 minutes | Coding time: 9 minutes

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 (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 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**.

This is a companion discussion topic for the original entry at http://iq.opengenus.org/kirkpatrick-seidel-algorithm-convex-hull/