Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Convex hull algorithms
open-in-new
<h2 id="planar-case">Planar case</h2> <p>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. </p><p>If not all points are on the same line, then their convex hull is a <a href="/facts/Convex_polygon/7x35w610">convex polygon</a> whose vertices are some of the points in the input set. 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 <a href="/facts/Half-space_(geometry)/AGknBgnw">half-planes</a>. </p> <h3>Lower bound on computational complexity</h3> <p>For a finite set of points in the plane, the lower bound on the computational complexity of finding the convex hull represented as a convex polygon is easily shown to be the same as for <a href="/facts/Sorting/olGzsItY">sorting</a> using the following <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduction</a>. For the set x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}} numbers to sort consider the set ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})} of points in the plane. Since they lie on a <a href="/facts/Parabola/Cweo3wgw">parabola</a>, which is a <a href="/facts/Convex_function/IbzG5SLF">convex curve</a>, it is easy to see that the vertices of the convex hull, when traversed along the boundary, produce the sorted order of the numbers x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}} . Clearly, <a href="/facts/Linear_time/77T62gmf">linear time</a> 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 <i>n</i> points cannot be computed more quickly than sorting. </p><p>The standard Ω(<i>n</i> log <i>n</i>) lower bound for sorting is proven in the <a href="/facts/Decision_tree_model/FalJqMSd">decision tree model</a> 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. Sorting also requires Ω(<i>n</i> log <i>n</i>) time in the <a href="/facts/Algebraic_decision_tree/FalJqMSd">algebraic decision tree</a> model of computation, a model that is more suitable for convex hulls, and in this model convex hulls also require Ω(<i>n</i> log <i>n</i>) time.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> However, in models of computer arithmetic that allow numbers to be sorted more quickly than <i>O</i>(<i>n</i> log <i>n</i>) time, for instance by using <a href="/facts/Integer_sorting/eItzeey5">integer sorting</a> algorithms, planar convex hulls can also be computed more quickly: the <a href="/facts/Graham_scan/WmFuJzEg">Graham scan</a> algorithm for convex hulls consists of a single sorting step followed by a linear amount of additional work. </p> <h3>Optimal output-sensitive algorithms</h3> <p>As stated above, the complexity of finding a convex hull as a function of the input size <i>n</i> is lower bounded by Ω(<i>n</i> log <i>n</i>). However, the complexity of some convex hull algorithms can be characterized in terms of both input size <i>n</i> and the output size <i>h</i> (the number of points in the hull). Such algorithms are called <a href="/facts/Output-sensitive_algorithm/5vAv585y">output-sensitive algorithms</a>. They may be asymptotically more efficient than Θ(<i>n</i> log <i>n</i>) algorithms in cases when <i>h</i> = <i>o</i>(<i>n</i>). </p><p>The lower bound on worst-case running time of output-sensitive convex hull algorithms was established to be Ω(<i>n</i> log <i>h</i>) in the planar case.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> There are several algorithms which attain this optimal <a href="/facts/Analysis_of_algorithms/pStoBgBn">time complexity</a>. The earliest one was introduced by <a href="/facts/David_G._Kirkpatrick/2qE9tdxA">Kirkpatrick</a> and <a href="/facts/Raimund_Seidel/u4XMgNom">Seidel</a> in 1986 (who called it "the <a href="/facts/Ultimate_convex_hull_algorithm/h2E4vCMN">ultimate convex hull algorithm</a>"). A much simpler algorithm was developed by <a href="/facts/Timothy_M._Chan/6fax6RRM">Chan</a> in 1996, and is called <a href="/facts/Chan%27s_algorithm/DyCgtttL">Chan's algorithm</a>. </p> <h3>Algorithms</h3> <p>Known convex hull algorithms are listed below, ordered by the date of first publication. Time complexity of each algorithm is stated in terms of the number of inputs points <i>n</i> and the number of points on the hull <i>h</i>. Note that in the worst case <i>h</i> may be as large as <i>n</i>. </p> <ul><li><a href="/facts/Gift_wrapping_algorithm/4V8z8eHC">Gift wrapping</a>, a.k.a. Jarvis march — <i>O</i>(<i>nh</i>) One of the simplest (although not the most time efficient in the worst case) planar algorithms. Created independently by Chand & Kapur in 1970 and R. A. Jarvis in 1973. It has <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>nh</i>) <a href="/facts/Analysis_of_algorithms/pStoBgBn">time complexity</a>, where <i>n</i> is the number of points in the set, and <i>h</i> is the number of points in the hull. In the worst case the complexity is <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>n2</i>).</li> <li><a href="/facts/Graham_scan/WmFuJzEg">Graham scan</a> — <i>O</i>(<i>n</i> log <i>n</i>) A slightly more sophisticated, but much more efficient algorithm, published by <a href="/facts/Ronald_Graham/ukKzczTL">Ronald Graham</a> in 1972. If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(<i>n</i>) time.</li> <li><a href="/facts/Quickhull/XEeXGNNr">Quickhull</a> Created independently in 1977 by W. Eddy and in 1978 by A. Bykat. Just like the <a href="/facts/Quicksort/1BeqhLAH">quicksort</a> algorithm, it has the expected time complexity of <i>O</i>(<i>n</i> log <i>n</i>), but may degenerate to <i>O</i>(<i>n</i>2) in the worst case.</li> <li>Divide and conquer, a.k.a. merge hull — <i>O</i>(<i>n</i> log <i>n</i>) Another O(<i>n</i> log <i>n</i>) algorithm, published in 1977 by <a href="/facts/Franco_P._Preparata/MDXAqRCW">Preparata</a> and Hong. This algorithm is also applicable to the three dimensional case. <a href="/facts/Timothy_M._Chan/6fax6RRM">Chan</a> calls this "one of the best illustrations of the power of the divide-and-conquer paradigm".<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li> <li>Monotone chain, a.k.a. Andrew's algorithm — <i>O</i>(<i>n</i> log <i>n</i>) Published in 1979 by A. M. Andrew. The algorithm can be seen as a variant of Graham scan which sorts the points lexicographically by their coordinates. When the input is already sorted, the algorithm takes <i>O</i>(<i>n</i>) time.</li> <li>Incremental convex hull algorithm — <i>O</i>(<i>n</i> log <i>n</i>) Published in 1984 by Michael Kallay.</li> <li><a href="/facts/Kirkpatrick%E2%80%93Seidel_algorithm/h2E4vCMN">Kirkpatrick–Seidel algorithm</a> — <i>O</i>(<i>n</i> log <i>h</i>) The first optimal output-sensitive algorithm. It modifies the divide and conquer algorithm by using the technique of marriage-before-conquest and <a href="/facts/LP-type_problem/4y1aVUoR">low-dimensional linear programming</a>. Published by <a href="/facts/David_G._Kirkpatrick/2qE9tdxA">Kirkpatrick</a> and <a href="/facts/Raimund_Seidel/u4XMgNom">Seidel</a> in 1986.</li> <li><a href="/facts/Chan%27s_algorithm/DyCgtttL">Chan's algorithm</a> — <i>O</i>(<i>n</i> log <i>h</i>) A simpler optimal output-sensitive algorithm created by <a href="/facts/Timothy_M._Chan/6fax6RRM">Chan</a> in 1996. It combines gift wrapping with the execution of an <i>O</i>(<i>n</i> log <i>n</i>) algorithm (such as Graham scan) on small subsets of the input.</li></ul> <h3>Akl–Toussaint heuristic</h3> <p>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 <a href="/facts/Selim_Akl/Wu5pBM5H">Selim Akl</a> and <a href="/facts/G._T._Toussaint/AN8GxkAS">G. T. Toussaint</a>, 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 <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>n</i>).) These four points form a <a href="/facts/Quadrilateral/QCGqrkp2">convex quadrilateral</a>, 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(<i>n</i>), and thus, the entire operation is O(<i>n</i>). 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 <i>throw-away</i> 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 <i>n</i>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h3>On-line and dynamic convex hull problems</h3> <p>The discussion above considers the case when all input points are known in advance. One may consider two other settings.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <ul><li>Online convex hull problem: Input points are obtained sequentially one by one. After each point arrives on input, the convex hull for the pointset obtained so far must be efficiently computed.</li> <li><a href="/facts/Dynamic_convex_hull/FXwqnjf9">Dynamic convex hull</a> maintenance: The input points may be sequentially inserted or deleted, and the convex hull must be updated after each insert/delete operation.</li></ul> <p>Insertion of a point may increase the number of vertices of a convex hull at most by 1, while deletion may convert an <i>n</i>-vertex convex hull into an <i>n-1</i>-vertex one. </p><p>The online version may be handled with O(log <i>n</i>) per point, which is asymptotically optimal. The dynamic version may be handled with O(log2 <i>n</i>) per operation.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h3>Simple polygon</h3> <p class="note">Main article: <a href="/facts/Convex_hull_of_a_simple_polygon/ssfd5A1g">Convex hull of a simple polygon</a></p> <p>The convex hull of a <a href="/facts/Simple_polygon/C5CfrPWf">simple polygon</a> is divided by the polygon into pieces, one of which is the polygon itself and the rest are <i>pockets</i> bounded by a piece of the polygon boundary and a single hull edge. Although many algorithms have been published for the problem of constructing the convex hull of a simple polygon, nearly half of them are incorrect.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> McCallum and Avis provided the first correct algorithm.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> A later simplification by Graham & Yao (1983) and Lee (1983) uses only a single <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack data structure</a>. Their algorithm traverses the polygon clockwise, starting from its leftmost vertex. As it does, it stores a convex sequence of vertices on the stack, the ones that have not yet been identified as being within pockets. At each step, the algorithm follows a path along the polygon from the stack top to the next vertex that is not in one of the two pockets adjacent to the stack top. Then, while the top two vertices on the stack together with this new vertex are not in convex position, it pops the stack, before finally pushing the new vertex onto the stack. When the clockwise traversal reaches the starting point, the algorithm returns the sequence of stack vertices as the hull.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h2 id="higher-dimensions">Higher dimensions</h2> <p>A number of algorithms are known for the three-dimensional case, as well as for arbitrary dimensions.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> <a href="/facts/Chan%27s_algorithm/DyCgtttL">Chan's algorithm</a> is used for dimensions 2 and 3, and <a href="/facts/Quickhull/XEeXGNNr">Quickhull</a> is used for computation of the convex hull in higher dimensions.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p><p>For a finite set of points, the convex hull is a <a href="/facts/Convex_polyhedron/2pRHcRgC">convex polyhedron</a> in three dimensions, or in general a <a href="/facts/Convex_polytope/2pRHcRgC">convex polytope</a> for any number of dimensions, whose vertices are some of the points in the input set. 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 <a href="/facts/Face_(geometry)/T2E6BTU4">faces</a> is a non-trivial task, as is the dual problem of constructing the vertices given the faces. The size of the output face information may be exponentially larger than the size of the input vertices, and even in cases where the input and output are both of comparable size the known algorithms for high-dimensional convex hulls are not <a href="/facts/Output-sensitive_algorithm/5vAv585y">output-sensitive</a> due both to issues with degenerate inputs and with intermediate results of high complexity.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Orthogonal_convex_hull/XRxv9Qg1">Orthogonal convex hull</a></li></ul> <h2 id="further-reading">Further reading</h2> <ul><li><a href="/facts/Thomas_H._Cormen/qJ2Ys15T">Thomas H. Cormen</a>, <a href="/facts/Charles_E._Leiserson/6Uf19apB">Charles E. Leiserson</a>, <a href="/facts/Ronald_L._Rivest/nQsIcAKa">Ronald L. Rivest</a>, and <a href="/facts/Clifford_Stein/5ajkVbCm">Clifford Stein</a>. <i><a href="/facts/Introduction_to_Algorithms/o9n7KDsg">Introduction to Algorithms</a></i>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-262-03293-7. Section 33.3: Finding the convex hull, pp. 947–957.</li> <li><a href="/facts/Franco_P._Preparata/MDXAqRCW">Franco P. Preparata</a>, S.J. Hong. <i>Convex Hulls of Finite Sets of Points in Two and Three Dimensions</i>, Commun. ACM, vol. 20, no. 2, pp. 87–93, 1977.</li> <li><a href="/facts/Mark_de_Berg/SQt9z1vg">Mark de Berg</a>; <a href="/facts/Marc_van_Kreveld/Q26nPFw1">Marc van Kreveld</a>; <a href="/facts/Mark_Overmars/4MzGpDBq">Mark Overmars</a> & <a href="/facts/Otfried_Schwarzkopf/pE2cx5Qx">Otfried Schwarzkopf</a> (2000). <a href="https://archive.org/details/computationalgeo00berg"><i>Computational Geometry</i></a> (2nd revised ed.). <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-65620-3. Section 1.1: An Example: Convex Hulls (describes classical algorithms for 2-dimensional convex hulls). Chapter 11: Convex Hulls: pp. 235–250 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor).</li></ul> <h2 id="external-links">External links</h2> The Wikibook <i>Algorithm Implementation</i> has a page on the topic of: <i>Convex hull</i> <ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/ConvexHull.html">"Convex Hull"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li> <li><a href="https://www.cgal.org/Part/ConvexHullAlgorithms">2D, 3D, and dD Convex Hull</a> in <a href="/facts/CGAL/Dyyl9PGD">CGAL</a>, the Computational Geometry Algorithms Library</li> <li><a href="http://www.qhull.org/">Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection</a></li> <li><a href="https://web.archive.org/web/20101127013711/http://computacion.cs.cinvestav.mx/~anzures/geom/hull.html">Demo as Flash swf</a>, Jarvis, Graham, Quick (divide and conquer) and Chan algorithms</li> <li><a href="http://wayback.vefsafn.is/wayback/20130721095350/http://michal.is/projects/convex%2Dhull%2Dgift%2Dwrapping%2Dmethod/">Gift wrapping algorithm in C#</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms" <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms" <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Chan, Timothy. "A Minimalist's Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm" (PDF). Retrieved October 4, 2024. <a href="https://tmc.web.engr.illinois.edu/ch3d/ch3d.pdf" target="_blank">https://tmc.web.engr.illinois.edu/ch3d/ch3d.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Luc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366. <a href="/wiki/Luc_Devroye" target="_blank">/wiki/Luc_Devroye</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms" <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms" <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Aloupis, Greg. "A History of Linear-time Convex Hull Algorithms for Simple Polygons". Retrieved October 11, 2020. <a href="http://cgm.cs.mcgill.ca/~athens/cs601/" target="_blank">http://cgm.cs.mcgill.ca/~athens/cs601/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>McCallum, Duncan; Avis, David (1979), "A linear algorithm for finding the convex hull of a simple polygon", Information Processing Letters, 9 (5): 201–206, doi:10.1016/0020-0190(79)90069-3, MR 0552534 <a href="/wiki/David_Avis" target="_blank">/wiki/David_Avis</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Graham, Ronald L.; Yao, F. Frances (1983), "Finding the convex hull of a simple polygon", Journal of Algorithms, 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR 0729228 <a href="/wiki/Ronald_Graham" target="_blank">/wiki/Ronald_Graham</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Lee, D. T. (1983), "On finding the convex hull of a simple polygon", International Journal of Computer and Information Sciences, 12 (2): 87–98, doi:10.1007/BF00993195, MR 0724699, S2CID 28600832 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>See David Mount's Lecture Notes, including Lecture 4 for recent developments, including Chan's algorithm. <a href="/wiki/David_Mount" target="_blank">/wiki/David_Mount</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). "The quickhull algorithm for convex hulls" (PDF). ACM Transactions on Mathematical Software. 22 (4): 469–483. doi:10.1145/235815.235821. <a href="http://www.cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf" target="_blank">http://www.cise.ufl.edu/~ungor/courses/fall06/papers/QuickHull.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Avis, David; Bremner, David; Seidel, Raimund (1997), "How good are convex hull algorithms?", Computational Geometry: Theory and Applications, 7 (5–6): 265–301, doi:10.1016/S0925-7721(96)00023-5. <a href="/wiki/David_Avis" target="_blank">/wiki/David_Avis</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> </ol>