Editing Simple polygon (section)

== Related constructions ==
According to the [[Riemann mapping theorem]], any simply connected open subset of the plane can be [[conformal map|conformally mapped]] onto a disk. [[Schwarz–Christoffel mapping]] provides a method to explicitly construct a map from a disk to any simple polygon using specified vertex angles and pre-images of the polygon vertices on the boundary of the disk. These ''pre-vertices'' are typically computed numerically.{{r|trefethen-driscoll}}

[[File:GLPK solution of a travelling salesman problem.svg|thumb|The black polygon is the shortest loop connecting every red dot, a solution to the traveling salesperson problem.]]

Every finite set of points in the plane that does not lie on a single line can be connected to form the vertices of a simple polygon (allowing 180° angles); for instance, one such polygon is the solution to the [[traveling salesperson problem]].{{r|quintas-supnick}} Connecting points to form a polygon in this way is called [[polygonalization]].{{r|dfkkm}}

Every simple polygon can be represented by a formula in [[constructive solid geometry]] that constructs the polygon (as a closed set including the interior) from unions and intersections of [[half-plane]]s, with each side of the polygon appearing once as a half-plane in the formula. Converting an <math>n</math>-sided polygon into this representation can be performed in time <math>O(n\log n)</math>.{{r|dghs}}

The [[visibility graph]] of a simple polygon connects its vertices by edges representing the sides and diagonals of the polygon.{{r|everett-corneil}} It always contains a [[Hamiltonian cycle]], formed by the polygon sides. The computational complexity of reconstructing a polygon that has a given graph as its visibility graph, with a specified Hamiltonian cycle as its cycle of sides, remains an open problem.{{r|ghosh-goswami}}