Polygonalization

Last updated

16 polygonalizations of a set of six points 16 polygonalizations.svg
16 polygonalizations of a set of six 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. [1] A polygonalization may also be called a polygonization, [2] simple polygonalization, [3] Hamiltonian polygon, [4] non-crossing Hamiltonian cycle, [5] or crossing-free straight-edge spanning cycle. [6]

Contents

Every point set that does not lie on a single line has at least one polygonalization, which can be found in polynomial time. For points in convex position, there is only one, but for some other point sets there can be exponentially many. Finding an optimal polygonalization under several natural optimization criteria is a hard problem, including as a special case the travelling salesman problem. The complexity of counting all polygonalizations remains unknown.

Definition

A polygonalization is a simple polygon having a given set of points in the Euclidean plane as its set of vertices. A polygon may be described by a cyclic order on its vertices, which are connected in consecutive pairs by line segments, the edges of the polygon. A polygon, defined in this way, is "simple" if the only intersection points of these line segments are at shared endpoints. [2]

Some authors only consider polygonalizations for points that are in general position, meaning that no three are on a line. [7] With this assumption, the angle between two consecutive segments of the polygon cannot be 180°. However, when point sets with collinearities are considered, it is generally allowed for their polygonalizations to have 180° angles at some points. When this happens, these points are still considered to be vertices, rather than being interior to edges. [8]

Existence

Polygonalizations of a 3 x 3 grid. The 180deg angles visible in each polygon are necessary: for a grid of this size, all polygonalizations have a 180deg angle. 3x3 grid polygonalizations.svg
Polygonalizations of a 3 × 3 grid. The 180° angles visible in each polygon are necessary: for a grid of this size, all polygonalizations have a 180° angle.

Steinhaus (1964) observed that every finite point set with no three in a line forms the vertices of a simple polygon. [10] However, requiring no three to be in a line is unnecessarily strong. Instead, all that is required for the existence of a polygonalization (allowing 180° angles) is that the points do not all lie on one line. If they do not, then they have a polygonalization that can be constructed in polynomial time. One way of constructing a polygonalization is to choose any point in the convex hull of (not necessarily one of the given points). Then radially ordering the points around (breaking ties by distance from q) produces the cyclic ordering of a star-shaped polygon through all the given points, with in its kernel. [7] The same idea of sorting points radially around a central point is used in some versions of the Graham scan convex hull algorithm, and can be performed in time. [11] Polygonalizations that avoid 180° angles do not always exist. For instance, for 3 × 3 and 5 × 5 square grids, all polygonalizations use 180° angles. [9]

As well as star-shaped polygonalizations, every non-collinear set of points has a polygonalization that is a monotone polygon. This means that, with respect to some straight line (which may be taken as the -axis) every perpendicular line to the reference line intersects the polygon in a single interval, or not at all. A construction of Grünbaum (1994) begins by sorting the points by their -coordinates, and drawing a line through the two extreme points. Because the points are not all in a line, at least one of the two open halfplanes bounded by this line must be non-empty. Grünbaum forms two monotone polygonal chains connecting the extreme points through sorted subsequences of the points: one for the points in this non-empty open halfplane, and the other for the remaining points. Their union is the desired monotone polygon. After the sorting step, the rest of the construction may be performed in linear time. [4]

It is NP-complete to determine whether a set of points has a polygonalization using only axis-parallel edges. [12] However, polygonalizations with the additional constraint that they make a right turn at every vertex, if they exist, are uniquely determined. Each axis-parallel line through a point must pass through an even number of points, and this polygonalization must connect alternating pairs of points on this line. The polygonalization may be found in time by grouping the points by equal coordinates and sorting each group by the other coordinate. [13] For any point set, at most one rotation can have a polygonalization of this form, and this rotation can again be found in polynomial time. [14]

Optimization

Unsolved problem in mathematics:
What is the computational complexity of the longest polygonalization?
(more unsolved problems in mathematics)

Problems of finding an optimal polygonalization (for various criteria of optimality) are often computationally infeasible. For instance, the solution to the travelling salesman problem, for the given points, does not have any crossings. Therefore, it is always a polygonalization, the polygonalization with the minimum perimeter. [15] It is NP-hard to find. Similarly, finding the simple polygonalization with minimum or maximum area is known to be NP-hard, [3] and has been the subject of some computational efforts. [16] [17] The maximum area is always more than half of the area of the convex hull, giving an approximation ratio of 2. [18] The exact complexity of the simple polygonalization with maximum perimeter, and the existence of a constant approximation ratio for this problem, remain unknown. [5] The polygonalization that minimizes the length of its longest edge is also NP-hard to find, and hard to approximate to an approximation ratio better than ; no constant-factor approximation is known. [19]

A non-optimal solution to the travelling salesman problem may have crossings, but it is possible to eliminate all crossings by local optimization steps that reduce the total length. Using steps that also eliminate crossings at each step, this can be done in polynomial time, [20] but without this restriction there exist local optimization sequences that instead use an exponential number of steps. [21]

The shortest bitonic tour (the minimum-perimeter monotone polygon through the given points) is always a polygonalization, and can be found in polynomial time. [22]

Counting

Unsolved problem in mathematics:
What is the computational complexity of counting polygonalizations?
(more unsolved problems in mathematics)

The problem of counting all polygonalizations of a given point set belongs to #P, the class of counting problems associated with decision problems in NP. However, it is unknown whether it is #P-complete or, if not, what its computational complexity might be. [23] [24] A set of points has exactly one polygonalization if and only if it is in convex position. [1] There exist sets of points for which the number of polygonalizations is as large as , [25] and every set of points has at most polygonalizations. [6]

Methods applying the planar separator theorem to labeled triangulations of the points can be used to count all polygonalizations of a set of points in subexponential time, . [26] Dynamic programming can be used to count all monotone polygonalizations in polynomial time, and the results of this computation can then be used to generate a random monotone polygonalization. [27]

Generation

Unsolved problem in mathematics:
Can local moves connect the state space of polygonalizations for every point set?
(more unsolved problems in mathematics)
A polygon that cannot be changed into any other polygon through the same points by flips or VE-flips Unflippable polygon.svg
A polygon that cannot be changed into any other polygon through the same points by flips or VE-flips

It is unknown whether it is possible for the system of all polygonalizations to form a connected state space under local moves that change a bounded number of the edges of the polygonalizations. If this were possible, it could be used as part of an algorithm for generating all polygonalizations, by applying a graph traversal to the state space. For this problem, it is insufficient to consider flips that remove two edges of a polygonalization and replace them by two other edges, or VE-flips that remove three edges, two of which share a vertex, and replace them by three other edges. There exist polygonalizations for which no flip or VE-flip is possible, even though the same point set has other polygonalizations. [28]

The polygonal wraps, weakly simple polygons that use each given point one or more times as a vertex, include all polygonalizations and are connected by local moves. [2] Another more general class of polygons, the surrounding polygons, are simple polygons that have some of the given points as vertices and enclose all of the points. They are again locally connected, and can be listed in polynomial time per polygon. The algorithm constructs a tree of polygons, with the convex hull as its root and with the parent of each other surrounding polygon obtained by removing one vertex (proven to be possible by applying the two ears theorem to the exterior of the polygon). It then applies a reverse-search algorithm to this tree to list the polygons. As a consequence of this method, all polygonalizations can be listed in exponential time ( for points) and polynomial space. [29]

Applications

Classical connect the dots puzzles involve connecting points in sequence to form some unexpected shape, often without crossings. [30] The travelling salesman problem and its variants have many applications. [31] Polygonalization also has applications in the reconstruction of contour lines from scattered data points, and in boundary tracing in image analysis. [32]

See also

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, 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">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">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

<span class="mw-page-title-main">Euclidean minimum spanning tree</span> Shortest network connecting points

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

<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, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

<span class="mw-page-title-main">Point-set triangulation</span> Simplicial complex in Euclidean geometry

A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.

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

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

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">Monotone polygon</span>

In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects the boundary of P at most twice.

<span class="mw-page-title-main">Polygonal chain</span> Connected series of line segments

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 called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.

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

In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice.

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">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In discrete and computational geometry, a set of points in the Euclidean plane or a higher-dimensional Euclidean space is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the others. A finite set of points is in convex position if all of the points are vertices of their convex hull. More generally, a family of convex sets is said to be in convex position if they are pairwise disjoint and none of them is contained in the convex hull of the others.

<span class="mw-page-title-main">Opaque set</span> Shape that blocks all lines of sight

In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

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 Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003), "On the reflexivity of point sets", in Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 139–156, doi:10.1007/978-3-642-55566-4_6, ISBN   978-3-642-62442-1, MR   2038472
  2. 1 2 3 Damian, Mirela; Flatland, Robin; O'Rourke, Joseph; Ramaswami, Suneeta (2010), "Connecting polygonizations via stretches and twangs", Theory of Computing Systems , 47 (3): 674–695, arXiv: 0709.1942 , doi:10.1007/s00224-009-9192-8, MR   2652036, S2CID   59602
  3. 1 2 Fekete, S. P. (2000), "On simple polygonalizations with optimal area", Discrete & Computational Geometry , 23 (1): 73–110, doi:10.1007/PL00009492, MR   1727124, S2CID   15835121
  4. 1 2 Grünbaum, Branko (1994), "Hamiltonian polygons and polyhedra" (PDF), Geombinatorics , 3 (3): 83–89, MR   1326479
  5. 1 2 Dumitrescu, Adrian; Tóth, Csaba D. (2010), "Long non-crossing configurations in the plane", Discrete & Computational Geometry , 44 (4): 727–752, arXiv: 0909.4094 , doi: 10.1007/s00454-010-9277-9 , MR   2728029, S2CID   2813190
  6. 1 2 Sharir, Micha; Sheffer, Adam; Welzl, Emo (2013), "Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique", Journal of Combinatorial Theory , Series A, 120 (4): 777–794, arXiv: 1109.5596 , doi: 10.1016/j.jcta.2013.01.002 , MR   3022612
  7. 1 2 Deneen, Linda; Shute, Gary (1988), "Polygonizations of point sets in the plane", Discrete & Computational Geometry , 3 (1): 77–87, doi: 10.1007/BF02187898 , MR   0918181
  8. ↑ Malkevitch, Joseph (2016), "Are Precise Definitions a Good Idea?", AMS Feature Column, American Mathematical Society
  9. 1 2 Chow, Sam; Gafni, Ayla; Gafni, Paul (March 2021), "Connecting the dots: maximal polygons on a square grid", Mathematics Magazine , 94 (2): 118–124, doi:10.1080/0025570x.2021.1869493, MR   4241975, S2CID   233185771
  10. ↑ Steinhaus, Hugo (1964), One Hundred Problems in Elementary Mathematics, Basic Books, pp. 17, 85–86, ISBN   9780486811802
  11. ↑ Graham, R. L. (June 1972), "An efficient algorithm for determining the convex hull of a finite planar set" (PDF), Information Processing Letters , 1 (4): 132–133, doi:10.1016/0020-0190(72)90045-2
  12. ↑ Rappaport, David (1986), On the complexity of computing orthogonal polygons from a set of points, Technical Report, vol. SOCS-86.9, Montreal: McGill University
  13. ↑ O'Rourke, Joseph (1988), "Uniqueness of orthogonal connect-the-dots", in Toussaint, Godfried T. (ed.), Computational Morphology: A Computational Geometric Approach to the Analysis of Form, Machine Intelligence and Pattern Recognition, vol. 6, Amsterdam: North-Holland, pp. 97–104, doi:10.1016/B978-0-444-70467-2.50013-8, ISBN   978-0-444-70467-2, MR   0994001
  14. ↑ Löffler, Maarten; Mumford, Elena (2011), "Connected rectilinear graphs on point sets", Journal of Computational Geometry, 2 (1): 1–15, doi:10.20382/v2i1a1, MR   2786032
  15. ↑ Quintas, L. V.; Supnick, Fred (1965), "On some properties of shortest Hamiltonian circuits", The American Mathematical Monthly , 72 (9): 977–980, doi:10.2307/2313333, JSTOR   2313333, MR   0188872
  16. ↑ Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph S. B. (2022), "Area-optimal simple polygonalizations: the CG challenge 2019", ACM Journal of Experimental Algorithmics, 27: Art. 2.4, 12, doi: 10.1145/3504000 , hdl: 1721.1/146480 , MR   4390039, S2CID   244117500
  17. ↑ Ramos, Natanael; de Rezende, Pedro J.; de Souza, Cid C. (2022), "Optimal area polygonization problems: exact solutions through geometric duality", Computers & Operations Research, 145, Paper No. 105842, doi:10.1016/j.cor.2022.105842, MR   4418151, S2CID   248369389
  18. ↑ Fekete, Sándor P. (1992), Geometry and the Travelling Salesman Problem (Doctoral dissertation), University of Waterloo, ProQuest   304035266 For a polygonalization of area more than half the convex hull, see Theorem 4.2.1, page 56.
  19. ↑ Fekete, Sándor P.; Keldenich, Phillip (2018), "Computing crossing-free configurations with minimum bottleneck" (PDF), 34th European Workshop on Computational Geometry, Free University of Berlin, pp. 23:1–23:6
  20. ↑ van Leeuwen, Jan; Schoone, Anneke A. (1981), "Untangling a travelling salesman tour in the plane" (PDF), in Mühlbacher, Jörg R. (ed.), Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981, Hanser, Munich, pp. 87–98, MR   0708744
  21. ↑ Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2014), "Worst case and probabilistic analysis of the 2-opt algorithm for the TSP", Algorithmica , 68 (1): 190–264, arXiv: 2302.06889 , doi: 10.1007/s00453-013-9801-4 , MR   3147481, S2CID   1638275
  22. ↑ de Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard (2016), "Fine-Grained Complexity Analysis of Two Classic TSP Variants", in Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:14, doi: 10.4230/LIPIcs.ICALP.2016.5 , ISBN   978-3-95977-013-2
  23. ↑ Mitchell, Joseph S. B.; O'Rourke, Joseph (2001), "Computational geometry column 42", International Journal of Computational Geometry and Applications , 11 (5): 573–582, arXiv: cs/0108021 , doi:10.1142/S0218195901000651, MR   1862888
  24. ↑ O'Rourke, Joseph (January 1, 2003), "Problem 16: Simple Polygonalizations", The Open Problems Project
  25. ↑ García, Alfredo; Noy, Marc; Tejel, Javier (2000), "Lower bounds on the number of crossing-free subgraphs of ", Computational Geometry: Theory & Applications , 16 (4): 211–221, doi: 10.1016/S0925-7721(00)00010-9 , MR   1775294
  26. ↑ Marx, Dániel; Miltzow, Tillmann (2016), "Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems", in Fekete, Sándor P.; Lubiw, Anna (eds.), 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 52:1–52:16, arXiv: 1603.07340 , doi: 10.4230/LIPIcs.SoCG.2016.52 , ISBN   9783959770095, MR   3540894, S2CID   7668194
  27. ↑ Zhu, Chong; Sundaram, Gopalakrishnan; Snoeyink, Jack; Mitchell, Joseph S. B. (1996), "Generating random polygons with given vertices", Computational Geometry: Theory & Applications , 6 (5): 277–290, doi: 10.1016/0925-7721(95)00031-3 , MR   1408922
  28. 1 2 Hernando, Carmen; Houle, Michael E.; Hurtado, Ferran (2002), "On local transformation of polygons with visibility properties", Theoretical Computer Science , 289 (2): 919–937, doi:10.1016/S0304-3975(01)00409-1, MR   1945256
  29. ↑ Yamanaka, Katsuhisa; Avis, David; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Algorithmic enumeration of surrounding polygons" (PDF), Discrete Applied Mathematics , 303: 305–313, doi:10.1016/j.dam.2020.03.034, MR   4310502
  30. ↑ Löffler, Maarten; Kaiser, Mira; van Kapel, Tim; Klappe, Gerwin; van Kreveld, Marc J.; Staals, Frank (2014), "The Connect-The-Dots family of puzzles: design and automatic generation", ACM Transactions on Graphics , 33 (4): 72:1–72:10, doi:10.1145/2601097.2601224, S2CID   9774101
  31. ↑ Cook, William J. (2012), "Chapter 3: The salesman in action", In pursuit of the traveling salesman, Princeton University Press, Princeton, NJ, pp. 44–61, ISBN   978-0-691-15270-7, MR   2866515
  32. ↑ Stelldinger, Peer (2010), "Connect the dots: the reconstruction of region boundaries from contour sampling points", in Köthe, Ullrich; Montanvert, Annick; Soille, Pierre (eds.), Applications of Discrete Geometry and Mathematical Morphology - First International Workshop, WADGMM 2010, Istanbul, Turkey, August 22, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7346, Springer, pp. 1–13, doi:10.1007/978-3-642-32313-3_1, ISBN   978-3-642-32312-6
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.