Convex hull: Difference between revisions

Content deleted Content added

Inline

Revision as of 16:25, 9 April 2008

In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X. (Note that X may be the union of any set of objects made of points).

To show this exists, it is necessary to see that every X is contained in at least one convex set (the whole space V, for example), and any intersection of convex sets containing X is also a convex set containing X. It is then clear that the convex hull is the intersection of all convex sets containing X, which is an alternative definition.

More directly, the convex hull of X can be described constructively as the set of convex combinations of points from X: that is, the set of points of the form $\sum _{j=1}^{n}t_{j}x_{j}$ , where n is an arbitrary natural number, the numbers $t_{j}$ are non-negative and sum to 1, and the points $x_{j}$ are in X. It is simple to check that this set satisfies either of the two definitions above.

In fact, if X is a subset of an N-dimensional vector space, sums of up to N+1 points are sufficient in the definition above. This is equivalent to saying that the convex hull is the union of all simplexes with vertices in X. This is known as Carathéodory's theorem.

The convex hull is defined for any kind of objects made up of points in a vector space, which may have any number of dimensions. The convex hull of finite sets of points and other geometrical objects in a two-dimensional plane or three-dimensional space are special cases of practical importance.

Intuitive picture

For planar objects, i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given objects; when released, it will assume the shape of the required convex hull.

It may seem natural to generalise this picture to higher dimensions by imagining the objects enveloped in a sort of idealised unpressurised elastic membrane or balloon under tension. However, the equilibrium (minimum-energy) surface in this case may not be the convex hull — parts of the resulting surface may have negative curvature, like a saddle surface. For the case of points in 3-dimensional space, if a rigid wire were first placed between each pair of points, then the balloon would take the form of the convex hull of the points.

Computation of convex hulls

In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities.

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.

Planar case

Finite 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 half-planes.

Jarvis march

The simplest (although not the most time efficient in the worst case) 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, where n is the number of points in the set, and h is the number of points in the hull. In the worst cases the complexity is O(n²)

Graham scan

A slightly more sophisticated, but much more efficient algorithm is the Graham scan, published in 1972 (O(n log n) time complexity). If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(n) time.

Divide and conquer

Another (O(n logn)) solution is the divide and conquer algorithm for the convex hull, published in 1977 by Preparata and Hong. This algorithm is also applicable to the three dimensional case.

Optimal output-sensitive algorithms

While it is not possible to do better than O(n log n) if we write the complexity only as a function of the input size n, we can obtain more efficient solutions by using an output-sensitive algorithm. There are two famous optimal output-sensitive algorithms for the planar case with O(n log h) time complexity, where h is the number of points in the hull. The earliest one is called the ultimate convex hull algorithm and was introduced by Kirkpatrick and Seidel in 1986, and uses the principle of marriage-before-conquest. A much simpler algorithm was developed by Chan in 1996, and is called Chan's algorithm.

Akl-Toussaint heuristics

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 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 is based on the following idea. Find the two points with the lowest and highest x-coordinates, and the two points with the lowest and highest y-coordinates. (Each of these operations takes O(n).) These four points form a convex 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 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.

Simple polygon

The convex hull of a simple polygon can be constructed in O(n) time. The basic idea is very simple. Starting from the leftmost vertex, at each step one looks at three consecutive vertices of the polygon. If the resulting angle is concave, then the middle point is discarded and the next (along the polygon) vertex is added to the triple to be tested. If the angle is convex, then the whole triple shifted by one vertex along the polygon. However quite a few published articles overlooked a possibility that deletion of a vertex from a polygon may result in a self-intersecting polygon, rendering further flow of the algorithm invalid. Fortunately, this case may also be handled efficiently.

Higher dimensions

For a finite set of points, the convex hull is a convex polyhedron in three dimensions, or in general a convex polytope for any number of dimensions. Its representation is not so simple as in the planar case, however. In higher dimensions, even if the vertices of a convex polytope 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. See also David Mount's Lecture Notes for comparison. Refer to Lecture 4 for the latest developments, including Chan's algorithm.

Relations to other geometric structures

The Delaunay triangulation of a point set (and the dual Voronoi Diagram) are closely related to convex hulls: the Delaunay triangulation of a point set in Rⁿ can be viewed as the projection of a convex hull in Rⁿ⁺¹ (Brown 1979).

The orthogonal convex hull of a point set is the intersection of all orthogonally convex supersets of the point set, where an orthogonally convex set is defined to intersect each axis-parallel line in a connected subset. Orthogonal convex hulls have properties similar to those of convex hulls, and can be constructed by algorithms with similar time bounds as those for convex hulls.

Applications

The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics and GIS. It also serves as a tool, a building block for a number of other computational-geometric algorithms. For example, consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance apart. The diameter will always be the distance between two points on the convex hull. The O(n lg n). algorithm for computing diameter proceeds by first constructing the convex hull, then for each hull vertex finding which other hull vertex is farthest away from it. This so-called "rotating-calipers" method can be used to move efficiently from one hull vertex to another.

References

Brown, K. Q. (1979). "Voronoi diagrams from convex hulls". Information Processing Letters. 9 (5): 223–228.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 33.3: Finding the convex hull, pp.947–957.

F.P. Preparata, S.J. Hong. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Commun. ACM, vol. 20, no. 2, pp. 87–93, 1977.

M. de Berg; M. van Kreveld; M. Overmars; O. Schwarzkopf. (2000). Computational Geometry, Algorithms and Applications. Springer.{{cite book}}: CS1 maint: multiple names: authors list (link)

External links

@@ Line 1: / Line 1: @@
-In [[mathematics]], the '''convex hull''' or '''convex envelope''' for a [[set]] of points ''X'' in a [[real]] [[vector space]] V is the minimal [[convex set]] containing ''X''.
 [[Image:ConvexHull.png|thumb|Convex hull: elastic band analogy]]
+In [[mathematics]], the '''convex hull''' or '''convex envelope''' for a set of points ''X'' in a [[real]] [[vector space]] V is the minimal [[convex set]] containing ''X''. (Note that ''X'' may be the union of any set of objects made of points).
+To show this exists, it is necessary to see that every ''X'' is contained in at least one convex set (the whole space ''V'', for example), and any intersection of convex sets containing ''X'' is also a convex set containing ''X''. It is then clear that the convex hull is the intersection of all convex sets containing ''X'', which is an alternative definition.
-==Intuitive picture==
-For ''planar objects'', i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.
-It may seem natural to generalise this picture to higher dimensions by imagining the objects enveloped in a sort of idealised unpressurised elastic membrane or balloon under tension. However, the equilibrium (minimum-energy) surface in this case may not be the convex hull — parts of the resulting surface may have negative [[curvature]], like a [[saddle surface]]. For the case of points in 3-dimensional space, if a rigid wire is first placed between each pair of points, then the balloon will spring back under tension to take the form of the convex hull of the points.
-==Existence of the convex hull==
-To show that the convex hull of a set ''X'' in a real vector space ''V'' exists, notice that ''X'' is contained in at least one convex set (the whole space ''V'', for example), and any intersection of convex sets containing ''X'' is also a convex set containing ''X''. It is then clear that the convex hull is the intersection of all convex sets containing ''X''. This can be used as an alternative definition of the convex hull.
 More directly, the convex hull of ''X'' can be described constructively as the set of [[convex combination]]s of points from ''X'': that is, 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''. It is simple to check that this set satisfies either of the two definitions above.
-So the convex hull <math>H_\mathrm{convex}(X)</math> of set X is:
-<math>
-H_\mathrm{convex}(X) =\left\{\sum_{i=1}^k \alpha_i x_i \ \Bigg |  \ x_i\in X, \, \alpha_i\in \mathbb{R}, \, \alpha_i \geq 0, \, \sum_{i=1}^k \alpha_i=1,\, k=1, 2, \dots\right\}.
-</math>
-In fact, if ''X'' is a subset of an ''N''-dimensional vector space, sums of up to ''N''&nbsp;+&nbsp;1 points are sufficient in the definition above. This is equivalent to saying that the convex hull of ''X'' is the union of all [[simplex]]es with at most ''N''+1 vertices from X. This is known as [[Carathéodory's theorem (convex hull)|Carathéodory's theorem]].
+In fact, if ''X'' is a subset of an ''N''-dimensional vector space, sums of up to ''N''+1 points are sufficient in the definition above. This is equivalent to saying that the convex hull is the union of all [[simplex]]es with vertices in X. This is known as [[Carathéodory's theorem (convex hull)|Carathéodory's theorem]].
 The convex hull is defined for any kind of objects made up of points in a vector space, which may have any number of dimensions. The convex hull of finite sets of points and other geometrical objects in a two-dimensional plane or three-dimensional space are special cases of practical importance.
+==Intuitive picture==
-==Computation of convex hulls==
+For ''planar objects'', i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given objects; when released, it will assume the shape of the required convex hull.
+It may seem natural to generalise this picture to higher dimensions by imagining the objects enveloped in a sort of idealised unpressurised elastic membrane or balloon under tension. However, the equilibrium (minimum-energy) surface in this case may not be the convex hull — parts of the resulting surface may have negative [[curvature]], like a [[paraboloid|saddle surface]]. For the case of points in 3-dimensional space, if a rigid wire were first placed between each pair of points, then the balloon would take the form of the convex hull of the points.
-{{main|Convex hull algorithms}}
+==Computation of convex hulls==
 In [[computational geometry]], numerous algorithms are proposed for computing the convex hull of a finite set of points, with various [[computational complexity|computational complexities]].
 Computing the convex hull means that a non-ambiguous and efficient [[data structure|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.
+=== Planar case ===
+==== Finite 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 [[half-space|half-planes]].
+===== Jarvis march =====
+The simplest (although not the most time efficient in the worst case) algorithm in the plane was proposed by R.A. Jarvis in 1973. It is also called [[gift wrapping algorithm]]. It has [[Big O notation|O]](''nh'') [[computational complexity|time complexity]], where ''n'' is the number of points in the set, and ''h'' is the number of points in the hull. In the worst cases the complexity is [[Big O notation|O]](''n<sup>2'')
+===== Graham scan =====
+A slightly more sophisticated, but much more efficient algorithm is the [[Graham scan]], published in 1972 (O(''n'' log ''n'') time complexity). If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(''n'') time.
+===== Divide and conquer =====
+Another (O(''n'' log''n'')) solution is the [[divide and conquer algorithm]] for the convex hull, published in 1977 by Preparata and Hong. This algorithm is also applicable to the three dimensional case.
+===== Optimal output-sensitive algorithms =====
+While it is not possible to do better than O(''n'' log ''n'') if we write the complexity only as a function of the input size ''n'', we can obtain more efficient solutions by using an [[output-sensitive algorithm]]. There are two famous optimal output-sensitive algorithms for the planar case with O(''n'' log ''h'') [[computational complexity|time complexity]], where ''h'' is the number of points in the hull. The earliest one is called the [[ultimate convex hull algorithm]] and was introduced by [[David G. Kirkpatrick|Kirkpatrick]] and [[Raimund Seidel|Seidel]] in 1986, and uses the principle of [[marriage-before-conquest]]. A much simpler algorithm was developed by [[Timothy M. Chan|Chan]] in 1996, and is called [[Chan's algorithm]].
+===== Akl-Toussaint heuristics =====
+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 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 is based on the following idea.  Find the two points with the lowest and highest x-coordinates, and the two points with the lowest and highest y-coordinates. (Each of these operations takes [[Big O notation|O]](''n'').) These four points form a [[quadrilateral|convex 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 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.
+==== Simple polygon ====
+The convex hull of a [[simple polygon]] can be constructed in O(''n'') time. The basic idea is very simple. Starting from the leftmost vertex, at each step one looks at three consecutive vertices of the polygon. If the resulting angle is concave, then the middle  point is discarded and the next (along the polygon) vertex is added to the triple to be tested. If the angle is convex, then the whole triple shifted by one vertex along the polygon. However quite a few published articles overlooked a possibility that deletion of a vertex from a polygon may result in a self-intersecting polygon, rendering further flow of the algorithm invalid. Fortunately, this case may also be handled efficiently.
+=== Higher dimensions  ===
+For a finite set of points, the convex hull is a convex [[polyhedron]] in three dimensions, or in general a convex [[polytope]] for any number of dimensions.  Its representation is not so simple as in the planar case, however. In higher dimensions, even if the vertices of a convex polytope are known, construction of its [[face]]s 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.
+See also [http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf David Mount's Lecture Notes] for comparison. Refer to Lecture 4 for the latest developments, including
+[[Chan's algorithm]].
 == Relations to other geometric structures ==
-The [[Delaunay triangulation]] of a point set and its [[dual (mathematics)|dual]], the [[Voronoi Diagram]], are mathematically  related to convex hulls: the Delaunay triangulation of a point set in '''R'''<sup>''n''</sup> can be viewed as the projection of a convex hull in '''R'''<sup>''n''+1</sup> (Brown 1979).
+The [[Delaunay triangulation]] of a point set (and the dual [[Voronoi Diagram]]) are closely related to convex hulls: the Delaunay triangulation of a point set in '''R'''<sup>n</sup> can be viewed as the projection of a convex hull in '''R'''<sup>n+1</sup> (Brown 1979).
 The [[orthogonal convex hull]] of a point set is the intersection of all orthogonally convex supersets of the point set, where an orthogonally convex set is defined to intersect each axis-parallel line in a connected subset. Orthogonal convex hulls have properties similar to those of convex hulls, and can be constructed by algorithms with similar time bounds as those for convex hulls.
@@ Line 37: / Line 66: @@
 == Applications ==
-The problem of finding convex hulls finds its practical applications in [[pattern recognition]], [[image processing]], [[statistics]] and [[GIS]]. It also serves as a tool, a building block for a number of other computational-geometric algorithms.  For example, consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance apart. The diameter will always be the distance between two points on the convex hull. The ''O''(''n'' log ''n'') algorithm for computing diameter proceeds by first constructing the convex hull, then for each hull vertex finding which other hull vertex is farthest away from it. This so-called "rotating-calipers" method can be used to move efficiently from one hull vertex to another.
+The problem of finding convex hulls finds its practical applications in [[pattern recognition]], [[image processing]], [[statistics]] and [[GIS]]. It also serves as a tool, a building block for a number of other computational-geometric algorithms.  For example, consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance apart. The diameter will always be the distance between two points on the convex hull. The ''O''(''n'' lg ''n''). algorithm for computing diameter proceeds by first constructing the convex hull, then for each hull vertex finding which other hull vertex is farthest away from it. This so-called "rotating-calipers" method can be used to move efficiently from one hull vertex to another.
 ==See also==
@@ Line 58: / Line 87: @@
 * [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 33.3: Finding the convex hull, pp.947&ndash;957.
-* [[Franco P. Preparata]], [[S.J. Hong]]. ''Convex Hulls of Finite Sets of Points in Two and Three Dimensions'', Commun. ACM, vol. 20, no. 2, pp. 87&ndash;93, 1977.
+* [[F.P. Preparata]], [[S.J. Hong]]. ''Convex Hulls of Finite Sets of Points in Two and Three Dimensions'', Commun. ACM, vol. 20, no. 2, pp. 87&ndash;93, 1977.
 * {{cite book
-  | author = M. de Berg; M. van Kreveld; [[Mark Overmars]]; O. Schwarzkopf.
+  | author = M. de Berg; M. van Kreveld; M. Overmars; O. Schwarzkopf.
   | title = Computational Geometry, Algorithms and Applications
   | publisher = Springer
@@ Line 68: / Line 97: @@
 ==External links==
 * [http://www.voronoi3d.com/index.html Applet for calculation and visualization of convex hull, Delaunay triangulations and Voronoi diagrams in space]
+* [http://mathworld.wolfram.com/ConvexHull.html Mathworld on convex hull]
-*  {{MathWorld | urlname=ConvexHull | title=Convex Hull}}
+* [http://www.qhull.org Qhull for computing the convex hull in 2-d, 3-d, etc.]
-* [http://demonstrations.wolfram.com/ConvexHull/ "Convex Hull"] by [[Eric W. Weisstein]], [[The Wolfram Demonstrations Project]], 2007.
-* [http://www.cgal.org/Part/ConvexHullAlgorithms  2D, 3D, and dD Convex Hull] in [[CGAL]], the Computational Geometry Algorithms Library
+* [http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/packages.html#Part:ConvexHullAlgorithms  Convex Hull Algorithms in CGAL, the Computational Geometry Algorithms Library]
-* [http://www.qhull.org/ Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection]
-* [http://www.microplop.com/2007/11/coursework-hell-convex-hull.html C++ Code and Reports for Convex Hull]
 [[Category:Convex geometry]]
 [[Category:Real analysis]]
+[[Category:Geometric algorithms]]
 [[Category:Polytopes]]
-[[Category:Closure operators]]
 [[de:Konvexe Hülle]]
 [[eo:Konveksa koverto]]
-[[es:Envoltura convexa]]
 [[fr:Enveloppe convexe]]
 [[it:Inviluppo convesso]]
@@ Line 90: / Line 116: @@
 [[sl:Konveksna ogrinjača]]
 [[sv:Konvext område]]
 [[vi:Bao lồi]]
 [[zh:凸包]]