Polygonalization

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]

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.

  1. ^ Cite error: The named reference reflexivity was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference dfor was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference fekete was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference grunbaum was invoked but never defined (see the help page).
  5. ^ Cite error: The named reference long was invoked but never defined (see the help page).
  6. ^ Cite error: The named reference ssw was invoked but never defined (see the help page).