<p>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 <span class="math-container">$1$</span> (and hence connect two horizontally or vertically adjacent lattice points.</p>
<p>The grid graph has a Hamiltonian cycle, if and only if the corresponding <span class="math-container">$n$</span> lattice points (interpreted as geometric points) have a polygonization with perimeter <span class="math-container">$n$</span>.</p>
<blockquote>
<p>Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter:<br />
Hamilton Paths in Grid Graphs.<br />
SIAM Journal on Computing 11, pp 676-686 (1982)</p>
</blockquote>

CC BY-SA 4.0
2020-11-21T21:48:41.880Z
Thanks, for your nice answer.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-11-21T22:10:14.500Z
Doesn't this also prove the NP-hardness of Maximum TSP for Euclidean distances?
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-11-22T17:46:45.597Z
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
CC BY-SA 4.0
2020-11-21T18:17:11.127Z
2020-11-21T18:17:11.127Z
Gamow
<p>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 <a href="https://link.springer.com/article/10.1007/PL00009492#page-1" rel="nofollow noreferrer">polygonization with minimum (or maximum)</a> enclosed area is NP-complete. The answer to this <a href="https://cstheory.stackexchange.com/questions/44354/complexity-of-existence-of-simple-polygonalization-with-prescribed-area">post</a> shows that it is NP-complete to decide the existence of a polygonization with some prescribed area.</p>
<p>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 <a href="https://dl.acm.org/doi/10.1145/876638.876640" rel="nofollow noreferrer">open problem</a>. The authors conjecture that the Maximum TSP for Euclidean distances in the plane is an NP-hard problem.</p>
<p>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?</p>

<cc.complexity-theory><np-hardness><cg.comp-geom><polygon>
How hard is deciding the existence of a polygonization with prescribed perimeter?
Mohammad Al-Turkistany
# How hard is deciding the existence of a polygonization with prescribed perimeter?

(Asked by: username_0 on 2020-11-21)

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)](https://link.springer.com/article/10.1007/PL00009492#page-1) enclosed area is NP-complete. The answer to this [post](https://cstheory.stackexchange.com/questions/44354/complexity-of-existence-of-simple-polygonalization-with-prescribed-area) 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](https://dl.acm.org/doi/10.1145/876638.876640). 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?

**Tags:** cc.complexity-theory, np-hardness, cg.comp-geom, polygon

---

## 1 answers

### Answer by username_1 on 2020-11-21. Score: 1 | Accepted 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)

> **Comments:**
> **username_0**: Thanks, for your nice answer.  
> **username_0**: Doesn't this also prove the NP-hardness of Maximum TSP for Euclidean distances?  
> **username_1**: 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.  

---

