Kirkpatrick-Seidel Algorithm (Ultimate Planar Convex Hull Algorithm)

algorithm
convex-hull
kirkpatrick-seidel-algorithm
ultimate-planar-convex-hull

(Team) #1

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/