Polygonalization
[6] Every point set that does not lie on a single line has at least one polygonalization, which can be found in polynomial time.
Finding an optimal polygonalization under several natural optimization criteria is a hard problem, including as a special case the travelling salesman problem.
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.
[8] Steinhaus (1964) observed that every finite point set with no three in a line forms the vertices of a simple polygon.
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.
(breaking ties by distance from q) produces the cyclic ordering of a star-shaped polygon through all the given points, with
[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
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.
For instance, the solution to the travelling salesman problem, for the given points, does not have any crossings.
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.
[18] The exact complexity of the simple polygonalization with maximum perimeter, and the existence of a constant approximation ratio for this problem, remain unknown.
[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.
[23][24] A set of points has exactly one polygonalization if and only if it is in convex position.
[6] Methods applying the planar separator theorem to labeled triangulations of the points can be used to count all polygonalizations of a set of
[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] 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.
They are again locally connected, and can be listed in polynomial time per 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 (
[31] Polygonalization also has applications in the reconstruction of contour lines from scattered data points, and in boundary tracing in image analysis.
