Convex hull of a simple polygon

Last updated
The convex hull of a simple polygon (blue). Its four pockets are shown in yellow; the whole region shaded in either color is the convex hull. Convex hull of a simple polygon.svg
The convex hull of a simple polygon (blue). Its four pockets are shown in yellow; the whole region shaded in either color is the convex hull.

In discrete geometry and computational geometry, the convex hull of a simple polygon is the polygon of minimum perimeter that contains a given simple polygon. It is a special case of the more general concept of a convex hull. It can be computed in linear time, faster than algorithms for convex hulls of point sets.

Contents

The convex hull of a simple polygon can be subdivided into the given polygon itself and into polygonal pockets bounded by a polygonal chain 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, this process eventually terminates with a convex polygon.

Structure

The convex hull of a simple polygon is itself a convex polygon. 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 polygonal chain 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. [1]

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. [1] This structure, called a convex differences tree, can be constructed efficiently. [2]

Algorithms

Finding the convex hull of a simple polygon can be performed in linear time. 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 McCallum & Avis (1979). [3] Even after its publication, other incorrect algorithms continued to be published. [4] Brönnimann & Chan (2006) write that a majority of the published algorithms for the problem are incorrect, [5] although a later history collected by Greg Aloupis lists only seven out of fifteen algorithms as being incorrect. [6]

A particularly simple algorithm for this problem was published by Graham & Yao (1983) and Lee (1983). Like the Graham scan 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. [7] [8] 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. [5]

A similar method can also be used to construct convex hulls of piecewise smooth closed curves in the plane. [9] By using a deque 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. [10]

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 Erdős–Nagy theorem, 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. [11]

Related Research Articles

<span class="mw-page-title-main">Polyhedron</span> 3D shape with flat faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.

<span class="mw-page-title-main">Convex hull</span> Smallest convex set containing a given set

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, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

<span class="mw-page-title-main">Convex polygon</span> Polygon that is the boundary of a convex set

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 simple polygon. Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, they are piecewise-linear Jordan curves consisting of finitely many line segments. They include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

<span class="mw-page-title-main">Straight skeleton</span> Method in geometry for representing a polygon by a topological skeleton

In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

A thrackle is an embedding of a graph in the plane in which each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be transverse.

<span class="mw-page-title-main">Pseudotriangle</span>

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

<span class="mw-page-title-main">Rotating calipers</span>

In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

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 pocket with respect to the boundary edge. The theorem is named after mathematicians Paul Erdős and Béla Szőkefalvi-Nagy.

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

<span class="mw-page-title-main">Two ears theorem</span> Every simple polygon with more than three vertices has at least two ears

In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equivalent to the existence of polygon triangulations. It is frequently attributed to Gary H. Meisters, but was proved earlier by Max Dehn.

In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the flip distance for triangulations of convex polygons.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.

References

  1. 1 2 Tor, S. B.; Middleditch, A. E. (1984), "Convex decomposition of simple polygons", ACM Transactions on Graphics , 3 (4): 244–265, doi: 10.1145/357346.357348
  2. ↑ Rappoport, Ari (1992), "An efficient adaptive algorithm for constructing the convex differences tree of a simple polygon", Computer Graphics Forum, 11 (4): 235–240, doi:10.1111/1467-8659.1140235
  3. ↑ 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
  4. ↑ Toussaint, Godfried (1991), "A counter-example to a convex hull algorithm for polygons", Pattern Recognition, 24 (2): 183–184, doi:10.1016/0031-3203(91)90087-L, MR   1087740
  5. 1 2 Brönnimann, Hervé; Chan, Timothy M. (2006), "Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time", Computational Geometry, 34 (2): 75–82, doi: 10.1016/j.comgeo.2005.11.005 , MR   2222883
  6. ↑ Aloupis, Greg, A History of Linear-time Convex Hull Algorithms for Simple Polygons, McGill University, retrieved 2020-01-01
  7. ↑ 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
  8. ↑ 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
  9. ↑ Schäffer, Alejandro A.; Van Wyk, Christopher J. (1987), "Convex hulls of piecewise-smooth Jordan curves", Journal of Algorithms, 8 (1): 66–94, doi:10.1016/0196-6774(87)90028-9, MR   0875326
  10. ↑ Melkman, Avraham A. (1987), "On-line construction of the convex hull of a simple polyline", Information Processing Letters , 25 (1): 11–12, doi:10.1016/0020-0190(87)90086-X, MR   0896397
  11. ↑ Demaine, Erik D.; Gassend, Blaise; O'Rourke, Joseph; Toussaint, Godfried T. (2008), "All polygons flip finitely ... right?", Surveys on discrete and computational geometry, Contemporary Mathematics, vol. 453, Providence, Rhode Island: American Mathematical Society, pp. 231–255, doi:10.1090/conm/453/08801, MR   2405683
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.