Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
Consider the general case when the input to the algorithm is a finite unordered set of points on a Cartesian plane.
An important special case, in which the points are given in the order of traversal of a simple polygon's boundary, is described later in a separate subsection.
In some applications it is convenient to represent a convex polygon as an intersection of a set of half-planes.
Clearly, linear time is required for the described transformation of numbers into points and then extracting their sorted order.
Therefore, in the general case the convex hull of n points cannot be computed more quickly than sorting.
The standard Ω(n log n) lower bound for sorting is proven in the decision tree model of computing, in which only numerical comparisons but not arithmetic operations can be performed; however, in this model, convex hulls cannot be computed at all.
As stated above, the complexity of finding a convex hull as a function of the input size n is lower bounded by Ω(n log n).
The lower bound on worst-case running time of output-sensitive convex hull algorithms was established to be Ω(n log h) in the planar case.
The earliest one was introduced by Kirkpatrick and Seidel in 1986 (who called it "the ultimate convex hull algorithm").
Time complexity of each algorithm is stated in terms of the number of inputs points n and the number of points on the hull h. Note that in the worst case h may be as large as n. The following simple heuristic is often used as the first step in implementations of convex hull algorithms to improve their performance.
It is based on the efficient convex hull algorithm by Selim Akl and G. T. Toussaint, 1978.
Optionally, the points with smallest and largest sums of x- and y-coordinates as well as those with smallest and largest differences of x- and y-coordinates can also be added to the quadrilateral, thus forming an irregular convex octagon, whose insides can be safely discarded.
If the points are random variables, then for a narrow but commonly encountered class of probability density functions, this throw-away pre-processing step will make a convex hull algorithm run in linear expected time, even if the worst-case complexity of the convex hull algorithm is quadratic in n.[3] The discussion above considers the case when all input points are known in advance.
Although many algorithms have been published for the problem of constructing the convex hull of a simple polygon, nearly half of them are incorrect.
[5] A later simplification by Graham & Yao (1983) and Lee (1983) uses only a single stack data structure.
When the clockwise traversal reaches the starting point, the algorithm returns the sequence of stack vertices as the hull.