Polygonalization

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. 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. Some authors only consider polygonalizations for points that are in general position, 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

Steinhaus (1964) 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. One way of constructing a polygonalization is to choose any point q {\displaystyle q} in the convex hull of P {\displaystyle P} (not necessarily one of the given points). Then radially ordering the points around q {\displaystyle q} (breaking ties by distance from q) produces the cyclic ordering of a star-shaped polygon through all the given points, with q {\displaystyle q} in its kernel. 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 O ( n log ⁡ n ) {\displaystyle O(n\log n)} time. Polygonalizations that avoid 180° angles do not always exist. For instance, for 3 × 3 and 5 × 5 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. This means that, with respect to some straight line (which may be taken as the x {\displaystyle x} -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 x {\displaystyle x} -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. It is NP-complete 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 O ( n log ⁡ n ) {\displaystyle O(n\log n)} 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

… excerpt ends here. Continue reading the full article.