discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geome ...

and

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, the convex hull of a simple polygon is the polygon of minimum perimeter that contains a given

simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise ...

. It is a special case of the more general concept of a

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

. It can be computed in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, faster than algorithms for convex hulls of point sets. The convex hull of a simple polygon can be subdivided into the given polygon itself and into polygonal ''pockets'' bounded by a

polygonal chain In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...

of the polygon together with a single convex hull edge. Repeatedly reflecting an arbitrarily chosen pocket across this convex hull edge produces a sequence of larger simple polygons; according to the

Erdős–Nagy theorem The Erdős–Nagy theorem is a result in discrete geometry stating that a non-convex simple polygon can be made into a convex polygon by a finite sequence of flips. The flips are defined by taking a convex hull of a polygon and reflecting a pock ...

, this process eventually terminates with a convex polygon.

Structure

The convex hull of a simple polygon is itself a

convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...

. Overlaying the original simple polygon onto its convex hull partitions this convex polygon into regions, one of which is the original polygon. The remaining regions are called ''pockets''. Each pocket is itself a simple polygon, bounded by a

on the boundary of the given simple polygon and by a single edge of the convex hull. A polygon that is already convex has no pockets. One can form a hierarchical description of any given polygon by constructing its hull and its pockets in this way and then recursively forming a hierarchy of the same type for each pocket. This structure, called a ''convex differences tree'', can be constructed efficiently.

Algorithms

Finding the convex hull of a simple polygon can be performed in

. Several early publications on this problem were discovered to be incorrect, often because they led to intermediate states with crossings that caused them to break. The first correct linear-time algorithm for this problem was given by . Even after its publication, other incorrect algorithms continued to be published. write that a majority of the published algorithms for the problem are incorrect, although a later history collected by Greg Aloupis lists only seven out of fifteen algorithms as being incorrect. A particularly simple algorithm for this problem was published by and . Like the

Graham scan Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(''n'' log ''n''). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices o ...

algorithm for convex hulls of point sets, it is based on a stack data structure. The algorithm traverses the polygon in clockwise order, starting from a vertex known to be on the convex hull (for instance, its leftmost point). 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. The points in this sequence are the vertices of a convex polygon (not necessarily the hull of all vertices seen so far) that may have pockets attached to some of its edges. 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 is completed and the stack contains the convex hull vertices in clockwise order. Each step of the algorithm either pushes a vertex onto the stack or pops it from the stack, and each vertex is pushed and popped at most once, so the total time for the algorithm is linear. If the input vertices are given in clockwise order in an array, then the output can be returned in the same array, using only a constant number of additional variables as intermediate storage. A similar method can also be used to construct convex hulls of

piecewise smooth In mathematics, a piecewise-defined function (also called a piecewise function, a hybrid function, or definition by cases) is a function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain. Pi ...

closed curves in the plane. By using a

deque In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). I ...

in place of a stack, a similar algorithm can be generalized to the convex hull of any polygonal chain, and the algorithm for simple polygons can be started at any vertex of the polygon rather than requiring an extreme vertex as the starting vertex.

Flipping pockets

A ''flip'' of a pocket constructs a new polygon from the given one by reflecting the polygonal chain that bounds a pocket across the convex hull edge of the pocket. Each flip produces another simple polygon with equal perimeter and greater area, although multiple simultaneous flips may introduce crossings. Flipping an arbitrarily chosen pocket, and then repeating this process with the pockets of each successively formed polygon, produces a sequence of simple polygons. According to the

, this flipping process eventually terminates, by reaching a convex polygon. As with the problem of convex hull construction, this problem has a long history of incorrect proofs.

References

{{reflist, refs= {{citation , last = Aloupis , first = Greg , accessdate = 2020-01-01 , publisher = McGill University , title = A History of Linear-time Convex Hull Algorithms for Simple Polygons , url = https://cgm.cs.mcgill.ca/~athens/cs601/ {{citation , last = Rappoport , first = Ari , doi = 10.1111/1467-8659.1140235 , issue = 4 , journal = Computer Graphics Forum , pages = 235–240 , title = An efficient adaptive algorithm for constructing the convex differences tree of a simple polygon , volume = 11 , year = 1992, s2cid = 20137707 {{citation , last = Toussaint , first = Godfried , authorlink = Godfried Toussaint , doi = 10.1016/0031-3203(91)90087-L , issue = 2 , journal = Pattern Recognition , mr = 1087740 , pages = 183–184 , title = A counter-example to a convex hull algorithm for polygons , volume = 24 , year = 1991, bibcode = 1991PatRe..24..183T {{citation , last1 = Demaine , first1 = Erik D. , author1-link = Erik Demaine , last2 = Gassend , first2 = Blaise , last3 = O'Rourke , first3 = Joseph , author3-link = Joseph O'Rourke (professor) , last4 = Toussaint , first4 = Godfried T. , author4-link = Godfried Toussaint , contribution = All polygons flip finitely ... right? , doi = 10.1090/conm/453/08801 , location = Providence, Rhode Island , mr = 2405683 , pages = 231–255 , publisher = American Mathematical Society , series = Contemporary Mathematics , title = Surveys on discrete and computational geometry , volume = 453 , year = 2008 {{citation , last = Lee , first = D. T. , authorlink = Der-Tsai Lee , doi = 10.1007/BF00993195 , issue = 2 , journal = International Journal of Computer and Information Sciences , mr = 724699 , pages = 87–98 , title = On finding the convex hull of a simple polygon , volume = 12 , year = 1983, s2cid = 28600832 {{citation , last1 = McCallum , first1 = Duncan , last2 = Avis , first2 = David , author2-link = David Avis , doi = 10.1016/0020-0190(79)90069-3 , issue = 5 , journal =

Information Processing Letters ''Information Processing Letters'' is a peer reviewed scientific journal in the field of computer science, published by Elsevier Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its ...

, mr = 552534 , pages = 201–206 , title = A linear algorithm for finding the convex hull of a simple polygon , volume = 9 , year = 1979 {{citation , last = Melkman , first = Avraham A. , doi = 10.1016/0020-0190(87)90086-X , issue = 1 , journal =

, mr = 896397 , pages = 11–12 , title = On-line construction of the convex hull of a simple polyline , volume = 25 , year = 1987 {{citation , last1 = Schäffer , first1 = Alejandro A. , last2 = Van Wyk , first2 = Christopher J. , doi = 10.1016/0196-6774(87)90028-9 , issue = 1 , journal = Journal of Algorithms , mr = 875326 , pages = 66–94 , title = Convex hulls of piecewise-smooth Jordan curves , volume = 8 , year = 1987 {{citation , last1 = Brönnimann , first1 = Hervé , last2 = Chan , first2 = Timothy M. , author2-link = Timothy M. Chan , doi = 10.1016/j.comgeo.2005.11.005 , issue = 2 , journal = Computational Geometry , mr = 2222883 , pages = 75–82 , title = Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time , volume = 34 , year = 2006, doi-access = free {{citation , last1 = Graham , first1 = Ronald L. , author1-link = Ronald Graham , last2 = Yao , first2 = F. Frances , author2-link = Frances Yao , doi = 10.1016/0196-6774(83)90013-5 , issue = 4 , journal =

Journal of Algorithms Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', ''Cell'', the ScienceDirect collection of electronic journals, '' Trends'', the ...

, mr = 729228 , pages = 324–331 , title = Finding the convex hull of a simple polygon , volume = 4 , year = 1983 {{citation , last1 = Tor , first1 = S. B. , last2 = Middleditch , first2 = A. E. , date = 1984 , doi = 10.1145/357346.357348 , issue = 4 , journal =

ACM Transactions on Graphics ''ACM Transactions on Graphics'' (TOG) is a bimonthly peer-reviewed scientific journal that covers the field of computer graphics. It was established in 1982 and is published by the Association for Computing Machinery. TOG publishes two special ...

, pages = 244–265 , title = Convex decomposition of simple polygons , volume = 3, doi-access = free Convex hulls Convex hull algorithms