|
In mathematics, the convex hull for an object or a set of
objects is the minimal convex set containing the given objects. It is the
minimal convex set because the convex hull is a subset of any convex set which contains the given objects.
The convex hull is defined for any kind of objects a and b for which linear combinations of the form
(1-t) a + t b are defined. Points in a two-dimensional plane and other geometrical objects
are special cases of practical importance.
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 the 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.
Planar case
Set of points
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.
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
The convex hull of a simple polygon may be constructed in O(n) time.
Higher dimensions
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. See http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html.
Relations to other geometric structures
See Delaunay triangulation
Applications
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.
|