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]
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.
- ^ Cite error: The named reference
reflexivitywas invoked but never defined (see the help page). - ^ Cite error: The named reference
dforwas invoked but never defined (see the help page). - ^ Cite error: The named reference
feketewas invoked but never defined (see the help page). - ^ Cite error: The named reference
grunbaumwas invoked but never defined (see the help page). - ^ Cite error: The named reference
longwas invoked but never defined (see the help page). - ^ Cite error: The named reference
sswwas invoked but never defined (see the help page).
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search