# How hard is deciding the existence of a polygonization with prescribed perimeter?

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?

## 1 Answer

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)

• Thanks, for your nice answer. – Mohammad Al-Turkistany Nov 21 '20 at 21:48
• Doesn't this also prove the NP-hardness of Maximum TSP for Euclidean distances? – Mohammad Al-Turkistany Nov 21 '20 at 22:10
• 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. – Gamow Nov 22 '20 at 17:46