Implementation of the Kirkpatrick–Seidel algorithm.
The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with O (nlogh) time complexity, where n 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.