Polygonalization on:
[Wikipedia]
[Google]
[Amazon]
In computational geometry, a polygonalization of a finite set of points in the
observed that every finite point set with no three in a line forms the vertices of a simple polygon. 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
It is unknown whether it is possible for the system of all polygonalizations to form a connected
reprinted
Dover Publications, 1979 & 2016, {{isbn, 9780486811802 {{citation , url = https://topp.openproblem.net/p16, title=Problem 16: Simple Polygonalizations , work = The Open Problems Project , last = O'Rourke , first = Joseph , author-link = Joseph O'Rourke (professor) , date = January 1, 2003 {{citation , last = Fekete , first = Sándor P. , id = {{ProQuest, 304035266 , publisher = University of Waterloo , title = Geometry and the Travelling Salesman Problem , type = Doctoral dissertation , year = 1992 For a polygonalization of area more than half the convex hull, see Theorem 4.2.1, page 56. {{citation , last1 = van Leeuwen , first1 = Jan , author1-link = Jan van Leeuwen , last2 = Schoone , first2 = Anneke A. , editor-last = Mühlbacher , editor-first = Jörg R. , contribution = Untangling a travelling salesman tour in the plane , contribution-url = https://webspace.science.uu.nl/~leeuw112/ruu-cs-80-11.pdf , mr = 0708744 , pages = 87–98 , publisher = Hanser, Munich , title = Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981 , year = 1981 {{citation , last1 = Yamanaka , first1 = Katsuhisa , last2 = Avis , first2 = David , author2-link = David Avis , last3 = Horiyama , first3 = Takashi , last4 = Okamoto , first4 = Yoshio , last5 = Uehara , first5 = Ryuhei , last6 = Yamauchi , first6 = Tanami , doi = 10.1016/j.dam.2020.03.034 , journal =
In computational geometry, a polygonalization of a finite set of points in the Euclidean plane
In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
is a 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 Piecewise linear curve, piecewise-linear Jordan curve consisting of finitely many line segments. The ...
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.
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 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 ot ...
, 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
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
. The complexity of counting all polygonalizations remains unknown.
Definition
A polygonalization is asimple 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 Piecewise linear curve, piecewise-linear Jordan curve consisting of finitely many line segments. The ...
having a given set of points in the Euclidean plane
In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
as its set of vertices. A polygon may be described by a cyclic order
In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. Ins ...
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.
Some authors only consider polygonalizations for points that are in general position
In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that a ...
, meaning that no three are on a line. 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.
Existence
observed that every finite point set with no three in a line forms the vertices of a simple polygon. 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
In theoretical 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 p ...
. One way of constructing a polygonalization is to choose any point in the convex hull
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, ...
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
In geometry, a star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.
Formally, a polygon is star-shaped if there exists a po ...
through all the given points, with in its kernel. The same idea of sorting points radially around a central point is used in some versions of 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 ...
convex hull algorithm, and can be performed in time. Polygonalizations that avoid 180° angles do not always exist. For instance, for and square grids, all polygonalizations use 180° angles.
As well as star-shaped polygonalizations, every non-collinear set of points has a polygonalization that is a monotone polygon
In geometry, a polygon in the plane is called monotone with respect to a straight line , if every line orthogonal to intersects the boundary of at most twice.
Similarly, a polygonal chain is called monotone with respect to a straight line ...
. 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 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 halfplane
In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space. If the space is two-dimensional, then a half-space is called a ''half-plane'' (open or closed). A half-space in a one-dimensiona ...
s bounded by this line must be non-empty. Grünbaum forms two monotone 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 ...
s 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
In theoretical 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 ...
.
It is NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
to determine whether a set of points has a polygonalization using only axis-parallel edges. 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. 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.
Optimization
Problems of finding an optimal polygonalization (for various criteria of optimality) are often computationally infeasible. For instance, the solution to thetravelling salesman problem
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
, for the given points, does not have any crossings. Therefore, it is always a polygonalization, the polygonalization with the minimum perimeter
A perimeter is the length of a closed boundary that encompasses, surrounds, or outlines either a two-dimensional shape or a one-dimensional line. The perimeter of a circle or an ellipse is called its circumference.
Calculating the perimet ...
. It is NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
to find. Similarly, finding the simple polygonalization with minimum or maximum area is known to be NP-hard, and has been the subject of some computational efforts. The maximum area is always more than half of the area of the convex hull
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, ...
, giving an approximation ratio
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
of 2. The exact complexity of the simple polygonalization with maximum perimeter, and the existence of a constant approximation ratio
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
for this problem, remain unknown. 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.
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
In theoretical 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 p ...
, but without this restriction there exist local optimization sequences that instead use an exponential number of steps.
The shortest bitonic tour
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.
Optimal bitonic tours
...
(the minimum-perimeter monotone polygon through the given points) is always a polygonalization, and can be found in polynomial time.
Counting
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. A set of points has exactly one polygonalization if and only if it is inconvex position 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 ot ...
. There exist sets of points for which the number of polygonalizations is as large as , and every set of points has at most polygonalizations.
Methods applying the planar separator theorem
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertic ...
to labeled triangulations of the points can be used to count all polygonalizations of a set of points in subexponential time, . 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.
Generation
It is unknown whether it is possible for the system of all polygonalizations to form a connected state space
In computer science, a state space is a discrete space representing the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial ...
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
In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversa ...
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.
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. 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
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, ...
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
In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two Ear (mathematics), ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equ ...
to the exterior of the polygon). It then applies a reverse-search algorithm 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 ...
to this tree to list the polygons. As a consequence of this method, all polygonalizations can be listed in exponential time
In theoretical 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 p ...
( for points) and polynomial space.
Applications
Classicalconnect the dots
Connect the dots (also known as connect-the-dots, dot to dot, join the dots or follow the dots) is a form of puzzle containing a sequence of numbered dots. When a line is drawn connecting the dots the outline of an object is revealed. The puzz ...
puzzles involve connecting points in sequence to form some unexpected shape, often without crossings. The travelling salesman problem and its variants have many applications. Polygonalization also has applications in the reconstruction of contour line
A contour line (also isoline, isopleth, isoquant or isarithm) of a Function of several real variables, function of two variables is a curve along which the function has a constant value, so that the curve joins points of equal value. It is a ...
s from scattered data points, and in boundary tracing
Boundary tracing, also known as contour tracing, of a binary digital region can be thought of as a segmentation technique that identifies the boundary pixels of the digital region. Boundary tracing is an important first step in the analysis of ...
in image analysis
Image analysis or imagery analysis is the extraction of meaningful information from images; mainly from digital images by means of digital image processing techniques. Image analysis tasks can be as simple as reading barcode, bar coded tags or a ...
.
See also
*Denjoy–Riesz theorem
In topology, the Denjoy–Riesz theorem states that every compact set of totally disconnected points in the Euclidean plane can be covered by a continuous image of the unit interval, without self-intersections (a Jordan arc).
Definitions and st ...
, on sets of infinitely many points that can be connected by a Jordan arc
References
{{reflist, refs= {{citation , last1 = Ramos , first1 = Natanael , last2 = de Rezende , first2 = Pedro J. , last3 = de Souza , first3 = Cid C. , doi = 10.1016/j.cor.2022.105842 , journal = Computers & Operations Research , mr = 4418151 , at = Paper No. 105842 , title = Optimal area polygonization problems: exact solutions through geometric duality , volume = 145 , year = 2022, s2cid = 248369389 {{citation , last1 = de Berg , first1 = Mark , author1-link = Mark de Berg , last2 = Buchin , first2 = Kevin , last3 = Jansen , first3 = Bart M. P. , last4 = Woeginger , first4 = Gerhard , author4-link = Gerhard J. Woeginger , editor1-last = Chatzigiannakis , editor1-first = Ioannis , editor2-last = Mitzenmacher , editor2-first = Michael , editor2-link = Michael Mitzenmacher , editor3-last = Rabani , editor3-first = Yuval , editor4-last = Sangiorgi , editor4-first = Davide , contribution = Fine-Grained Complexity Analysis of Two Classic TSP Variants , contribution-url = https://drops.dagstuhl.de/opus/volltexte/2016/6277 , doi = 10.4230/LIPIcs.ICALP.2016.5 , isbn = 978-3-95977-013-2 , location = Dagstuhl, Germany , pages = 5:1–5:14 , publisher = Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik , series = Leibniz International Proceedings in Informatics (LIPIcs) , title = 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) , volume = 55 , year = 2016, doi-access = free {{citation , last1 = Fekete , first1 = Sándor P. , last2 = Keldenich , first2 = Phillip , contribution = Computing crossing-free configurations with minimum bottleneck , contribution-url = https://conference.imp.fu-berlin.de/eurocg18/download/paper_23.pdf , pages = 23:1–23:6 , publisher = Free University of Berlin , title = 34th European Workshop on Computational Geometry , year = 2018 {{citation , last1 = Marx , first1 = Dániel , last2 = Miltzow , first2 = Tillmann , editor1-last = Fekete , editor1-first = Sándor P. , editor2-last = Lubiw , editor2-first = Anna , arxiv = 1603.07340 , contribution = Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems , doi = 10.4230/LIPIcs.SoCG.2016.52 , mr = 3540894 , pages = 52:1–52:16 , publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik , series = LIPIcs , title = 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA , volume = 51 , year = 2016, doi-access = free , isbn = 9783959770095 , s2cid = 7668194 {{citation , last1 = Mitchell , first1 = Joseph S. B. , author1-link = Joseph S. B. Mitchell , last2 = O'Rourke , first2 = Joseph , author2-link = Joseph O'Rourke (professor) , arxiv = cs/0108021 , doi = 10.1142/S0218195901000651 , issue = 5 , journal =International Journal of Computational Geometry and Applications
The ''International Journal of Computational Geometry and Applications'' (IJCGA) is a bimonthly journal published since 1991, by World Scientific. It covers the application of computational geometry in design and analysis of algorithms, focusing o ...
, mr = 1862888
, pages = 573–582
, title = Computational geometry column 42
, volume = 11
, year = 2001
{{citation
, last1 = Demaine , first1 = Erik D. , author1-link = Erik Demaine
, last2 = Fekete , first2 = Sándor P.
, last3 = Keldenich , first3 = Phillip
, last4 = Krupke , first4 = Dominik
, last5 = Mitchell , first5 = Joseph S. B. , author5-link = Joseph S. B. Mitchell
, doi = 10.1145/3504000
, journal = ACM Journal of Experimental Algorithmics
, mr = 4390039
, page = Art. 2.4, 12
, title = Area-optimal simple polygonalizations: the CG challenge 2019
, volume = 27
, year = 2022, s2cid = 244117500 , doi-access = free
, hdl = 1721.1/146480
, hdl-access = free
{{citation
, last = Stelldinger , first = Peer
, editor1-last = Köthe , editor1-first = Ullrich
, editor2-last = Montanvert , editor2-first = Annick
, editor3-last = Soille , editor3-first = Pierre
, contribution = Connect the dots: the reconstruction of region boundaries from contour sampling points
, doi = 10.1007/978-3-642-32313-3_1
, pages = 1–13
, publisher = Springer
, series = Lecture Notes in Computer Science
, title = Applications of Discrete Geometry and Mathematical Morphology - First International Workshop, WADGMM 2010, Istanbul, Turkey, August 22, 2010, Revised Selected Papers
, volume = 7346
, year = 2010, isbn = 978-3-642-32312-6
{{citation
, last1 = Löffler , first1 = Maarten
, last2 = Kaiser , first2 = Mira
, last3 = van Kapel , first3 = Tim
, last4 = Klappe , first4 = Gerwin
, last5 = van Kreveld , first5 = Marc J. , author5-link = Marc van Kreveld
, last6 = Staals , first6 = Frank
, doi = 10.1145/2601097.2601224
, 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.
The editor-in-chief is Carol O'Sullivan (Trinity College Dublin). According to the ''Journal Citation Reports'', th ...
, pages = 72:1–72:10
, title = The Connect-The-Dots family of puzzles: design and automatic generation
, volume = 33
, year = 2014, s2cid = 9774101
{{citation
, last1 = Damian , first1 = Mirela
, last2 = Flatland , first2 = Robin
, last3 = O'Rourke , first3 = Joseph , author3-link = Joseph O'Rourke (professor)
, last4 = Ramaswami , first4 = Suneeta
, doi = 10.1007/s00224-009-9192-8
, issue = 3
, journal = Theory of Computing Systems
''Theory of Computing Systems'' is a peer-reviewed scientific journal published by Springer Verlag.
Published since 1967 as ''Mathematical Systems Theory'' and since volume 30 in 1997 under its current title, it is devoted to publishing origina ...
, mr = 2652036
, pages = 674–695
, title = Connecting polygonizations via stretches and twangs
, volume = 47
, year = 2010, s2cid = 59602
, url = https://drops.dagstuhl.de/opus/volltexte/2008/1345/
, arxiv = 0709.1942
{{citation
, last1 = Englert , first1 = Matthias
, last2 = Röglin , first2 = Heiko
, last3 = Vöcking , first3 = Berthold
, doi = 10.1007/s00453-013-9801-4
, issue = 1
, journal = Algorithmica
''Algorithmica'' is a monthly peer-reviewed scientific journal focusing on research and the application of computer science algorithms. The journal was established in 1986 and is published by Springer Science+Business Media. The editor in chief i ...
, mr = 3147481
, pages = 190–264
, title = Worst case and probabilistic analysis of the 2-opt algorithm for the TSP
, volume = 68
, year = 2014, s2cid = 1638275
, doi-access = free
, arxiv = 2302.06889
{{citation
, last = Fekete , first = S. P.
, doi = 10.1007/PL00009492
, issue = 1
, journal = Discrete & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...
, mr = 1727124
, pages = 73–110
, title = On simple polygonalizations with optimal area
, volume = 23
, year = 2000, s2cid = 15835121
{{citation
, last1 = GarcÃa , first1 = Alfredo
, last2 = Noy , first2 = Marc
, last3 = Tejel , first3 = Javier
, doi = 10.1016/S0925-7721(00)00010-9
, issue = 4
, journal = Computational Geometry: Theory & Applications
, mr = 1775294
, pages = 211–221
, title = Lower bounds on the number of crossing-free subgraphs of
, volume = 16
, year = 2000, doi-access = free
{{citation
, last = Graham , first = R. L. , author-link = Ronald Graham
, date = June 1972
, doi = 10.1016/0020-0190(72)90045-2
, issue = 4
, journal = Information Processing Letters
''Information Processing Letters'' is a peer review, peer-reviewed scientific journal in the field of computer science, published by Elsevier. The aim of the journal is to enable fast dissemination of results in the field of Data processing, inform ...
, pages = 132–133
, title = An efficient algorithm for determining the convex hull of a finite planar set
, url = https://mathweb.ucsd.edu/~ronspubs/72_10_convex_hull.pdf
, volume = 1
{{citation
, last1 = Chow , first1 = Sam
, last2 = Gafni , first2 = Ayla
, last3 = Gafni , first3 = Paul
, date = March 2021
, doi = 10.1080/0025570x.2021.1869493
, issue = 2
, journal = Mathematics Magazine
''Mathematics Magazine'' is a refereed bimonthly publication of the Mathematical Association of America. Its intended audience is teachers of collegiate mathematics, especially at the junior/senior level, and their students. It is explicitly a j ...
, mr = 4241975
, pages = 118–124
, title = Connecting the dots: maximal polygons on a square grid
, volume = 94, s2cid = 233185771
{{citation
, last = Grünbaum , first = Branko , author-link = Branko Grünbaum
, issue = 3
, journal = Geombinatorics
Alexander Soifer is a Russian-born American mathematician and mathematics author.
Soifer obtained his Ph.D. in 1973 and has been a professor of mathematics at the University of Colorado since 1979. He was visiting fellow at Princeton University ...
, mr = 1326479
, pages = 83–89
, title = Hamiltonian polygons and polyhedra
, url = https://faculty.washington.edu/moishe/branko/BG194.Hamiltonian%20polyg%20&%20polyh.pdf
, volume = 3
, year = 1994
{{citation
, last1 = Hernando , first1 = Carmen
, last2 = Houle , first2 = Michael E.
, last3 = Hurtado , first3 = Ferran , author3-link = Ferran Hurtado
, doi = 10.1016/S0304-3975(01)00409-1
, issue = 2
, journal = Theoretical Computer Science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, mr = 1945256
, pages = 919–937
, title = On local transformation of polygons with visibility properties
, volume = 289
, year = 2002
{{citation
, last1 = Dumitrescu , first1 = Adrian
, last2 = Tóth , first2 = Csaba D.
, doi = 10.1007/s00454-010-9277-9
, issue = 4
, journal = Discrete & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...
, mr = 2728029
, pages = 727–752
, title = Long non-crossing configurations in the plane
, volume = 44
, year = 2010, s2cid = 2813190
, doi-access = free
, arxiv = 0909.4094
{{citation
, last = O'Rourke , first = Joseph , author-link = Joseph O'Rourke (professor)
, editor-last = Toussaint , editor-first = Godfried T. , editor-link = Godfried Toussaint
, contribution = Uniqueness of orthogonal connect-the-dots
, doi = 10.1016/B978-0-444-70467-2.50013-8
, location = Amsterdam
, mr = 994001
, pages = 97–104
, publisher = North-Holland
, series = Machine Intelligence and Pattern Recognition
, title = Computational Morphology: A Computational Geometric Approach to the Analysis of Form
, volume = 6
, year = 1988, isbn = 978-0-444-70467-2
{{citation
, last = Malkevitch , first = Joseph
, title = Are Precise Definitions a Good Idea?
, url = https://www.ams.org/publicoutreach/feature-column/fc-2016-01
, publisher = American Mathematical Society
, work = AMS Feature Column
, year = 2016
{{citation
, last = Cook , first = William J. , author-link = William J. Cook
, contribution = Chapter 3: The salesman in action
, isbn = 978-0-691-15270-7
, mr = 2866515
, pages = 44–61
, publisher = Princeton University Press, Princeton, NJ
, title = In pursuit of the traveling salesman
, year = 2012
{{citation
, last1 = Quintas , first1 = L. V.
, last2 = Supnick , first2 = Fred
, doi = 10.2307/2313333
, journal = The American Mathematical Monthly
''The American Mathematical Monthly'' is a peer-reviewed scientific journal of mathematics. It was established by Benjamin Finkel in 1894 and is published by Taylor & Francis on behalf of the Mathematical Association of America. It is an exposito ...
, jstor = 2313333
, mr = 188872
, pages = 977–980
, title = On some properties of shortest Hamiltonian circuits
, volume = 72
, year = 1965, issue = 9
{{citation
, last = Rappaport , first = David
, location = Montreal
, publisher = McGill University
, series = Technical Report
, title = On the complexity of computing orthogonal polygons from a set of points
, volume = SOCS-86.9
, year = 1986
{{citation
, last1 = Arkin , first1 = Esther M. , author1-link = Esther Arkin
, last2 = Fekete , first2 = Sándor P.
, last3 = Hurtado , first3 = Ferran , author3-link = Ferran Hurtado
, last4 = Mitchell , first4 = Joseph S. B. , author4-link = Joseph S. B. Mitchell
, last5 = Noy , first5 = Marc
, last6 = Sacristán , first6 = Vera
, last7 = Sethia , first7 = Saurabh
, editor1-last = Aronov , editor1-first = Boris , editor1-link = Boris Aronov
, editor2-last = Basu , editor2-first = Saugata
, editor3-last = Pach , editor3-first = János , editor3-link = János Pach
, editor4-last = Sharir , editor4-first = Micha , editor4-link = Micha Sharir
, contribution = On the reflexivity of point sets
, doi = 10.1007/978-3-642-55566-4_6
, mr = 2038472
, pages = 139–156
, publisher = Springer , location = Berlin
, series = Algorithms and Combinatorics
, title = Discrete and Computational Geometry: The Goodman-Pollack Festschrift
, volume = 25
, year = 2003, isbn = 978-3-642-62442-1
{{citation
, last1 = Löffler , first1 = Maarten
, last2 = Mumford , first2 = Elena
, doi = 10.20382/v2i1a1
, issue = 1
, journal = Journal of Computational Geometry
, mr = 2786032
, pages = 1–15
, title = Connected rectilinear graphs on point sets
, volume = 2
, year = 2011
{{citation
, last1 = Sharir , first1 = Micha , author1-link = Micha Sharir
, last2 = Sheffer , first2 = Adam
, last3 = Welzl , first3 = Emo , author3-link = Emo Welzl
, doi = 10.1016/j.jcta.2013.01.002
, issue = 4
, journal = Journal of Combinatorial Theory
The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...
, mr = 3022612
, pages = 777–794
, series = Series A
, title = Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
, volume = 120
, year = 2013, doi-access = free
, arxiv = 1109.5596
{{citation
, last1 = Deneen , first1 = Linda
, last2 = Shute , first2 = Gary
, doi = 10.1007/BF02187898
, issue = 1
, journal = Discrete & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...
, mr = 918181
, pages = 77–87
, title = Polygonizations of point sets in the plane
, volume = 3
, year = 1988, doi-access = free
{{citation, title=One Hundred Problems in Elementary Mathematics, first=Hugo, last=Steinhaus, author-link=Hugo Steinhaus, publisher=Basic Books, year=1964, pages=17, 85–86reprinted
Dover Publications, 1979 & 2016, {{isbn, 9780486811802 {{citation , url = https://topp.openproblem.net/p16, title=Problem 16: Simple Polygonalizations , work = The Open Problems Project , last = O'Rourke , first = Joseph , author-link = Joseph O'Rourke (professor) , date = January 1, 2003 {{citation , last = Fekete , first = Sándor P. , id = {{ProQuest, 304035266 , publisher = University of Waterloo , title = Geometry and the Travelling Salesman Problem , type = Doctoral dissertation , year = 1992 For a polygonalization of area more than half the convex hull, see Theorem 4.2.1, page 56. {{citation , last1 = van Leeuwen , first1 = Jan , author1-link = Jan van Leeuwen , last2 = Schoone , first2 = Anneke A. , editor-last = Mühlbacher , editor-first = Jörg R. , contribution = Untangling a travelling salesman tour in the plane , contribution-url = https://webspace.science.uu.nl/~leeuw112/ruu-cs-80-11.pdf , mr = 0708744 , pages = 87–98 , publisher = Hanser, Munich , title = Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981 , year = 1981 {{citation , last1 = Yamanaka , first1 = Katsuhisa , last2 = Avis , first2 = David , author2-link = David Avis , last3 = Horiyama , first3 = Takashi , last4 = Okamoto , first4 = Yoshio , last5 = Uehara , first5 = Ryuhei , last6 = Yamauchi , first6 = Tanami , doi = 10.1016/j.dam.2020.03.034 , journal =
Discrete Applied Mathematics
''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...
, mr = 4310502
, pages = 305–313
, title = Algorithmic enumeration of surrounding polygons
, url = http://cgm.cs.mcgill.ca/~avis/doc/avis/YAHOUY20.pdf
, volume = 303
, year = 2021
{{citation
, last1 = Zhu , first1 = Chong
, last2 = Sundaram , first2 = Gopalakrishnan
, last3 = Snoeyink , first3 = Jack
, last4 = Mitchell , first4 = Joseph S. B. , author4-link = Joseph S. B. Mitchell
, doi = 10.1016/0925-7721(95)00031-3
, issue = 5
, journal = Computational Geometry: Theory & Applications
, mr = 1408922
, pages = 277–290
, title = Generating random polygons with given vertices
, volume = 6
, year = 1996, doi-access = free
Polygons
Computational geometry