# 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?

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$$.