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?