Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or maximum) enclosed area is NP-complete. The answer to this post shows that it is NP-complete to decide the existence of a polygonization with some prescribed area.

Meanwhile, Minimum perimeter polygonization of 2D lattice points is a variant of the NP-complete Euclidean TSP. However, complexity of the maximization version of planar Euclidean TSP is an open problem. The authors conjecture that the Maximum TSP for Euclidean distances in the plane is an NP-hard problem.

I am interested in the complexity of deciding the existence of a polygonization of a set of 2D lattice points (in Euclidian plane) with prescribed perimeter. I suspect that it is NP-complete. What is known about its complexity?


Your problem is NP-hard, since it contains the Hamiltonian cycle problem on grid graphs as special case: Given a set of lattice points in the plane, is there a cycle in which all edges have lengths $1$ (and hence connect two horizontally or vertically adjacent lattice points.

The grid graph has a Hamiltonian cycle, if and only if the corresponding $n$ lattice points (interpreted as geometric points) have a polygonization with perimeter $n$.

Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter:
Hamilton Paths in Grid Graphs.
SIAM Journal on Computing 11, pp 676-686 (1982)

  • $\begingroup$ Thanks, for your nice answer. $\endgroup$ – Mohammad Al-Turkistany Nov 21 '20 at 21:48
  • $\begingroup$ Doesn't this also prove the NP-hardness of Maximum TSP for Euclidean distances? $\endgroup$ – Mohammad Al-Turkistany Nov 21 '20 at 22:10
  • $\begingroup$ No, because the result only yields the hardness of finding polygonizations where the perimeter is equal to the number of points. In the Maximum TSP, the perimeter will be much larger than the number of points. $\endgroup$ – Gamow Nov 22 '20 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.