Convex hull
|
|
ConvexHull.png
In mathematics, the convex hull or convex envelope 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.
If X is some set, the convex hull of X can be described as the set of points of the form <math>\sum_{j=1}^n t_jx_j<math>, where n is an arbitrary natural number, the numbers <math>t_j<math> are non-negative and sum to 1, and the points <math>x_j<math> are in X.
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 representation 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.
| Contents |
|
|
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
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.de:Konvexe Hülle ru:Выпуклая оболочка