For planar objects, i.e., lying in the plane, an easy way to visualize the convex hull is to imagine a rubber band tightly stretched to encompass given objects; when released, it will assume the shape of the required convex hull.
In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexity.
Computing the convex hull means that a non-ambiguous and efficient represesentation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.
| Table of contents |
|
2 Higher dimensions 3 Relations to other geometric structures 4 Applications |
If not all points are on the same line, then their convex hull is a convex polygon. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of halfplanes.
The convex hull of a simple polygon may be constructed in O(n) time.
For a finite set of points, the convex hull is a convex polyhedron. However its representation is not so simple as in the planar case. In higher dimensions, even if the vertices of a convex polyhedron are known, construction of its faces is a non-trivial task.
A number of algorithms are known for the three-dimensional case, as well as for arbitrary dimensions.
The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics. It also serves as a tool, a building block for a number of other computational-geometric algorithms.Planar case
Set of points
Jarvis march
The simplest (although not the most time efficient) algorithm in the plane was proposed by R.A. Jarvis in 1973. It is also called gift wrapping algorithm. It has O(nh) time complexity.Graham scan
A slightly more sophisticated, but much more efficient algorithm is the Graham scan, published in 1972 (O(n log n) time complexity).Akl-Toussaint heuristics
The following simple heuristics 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 S.Akl and G.T.Toussaint, 1978. The idea is to quickly exclude many points that would not be part of the convex hull anyway. This method works as follows: Find the two points with the lowest and highest x-coordinate, and the two points with the lowest and highest y-coordinate. (Each of these operations take O(n).) These four points form a quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n). (Optionally, the points with lowest and highest added x- and y-coordinate as well as those with lowest and highest subtracted x- and y-coordinate can also be determined and added, thus forming an irregular octagon, etc.)Simple polygon
Higher dimensions
Relations to other geometric structures
Applications