<p>The problem of comparing the lengths of two paths of line segments connecting points in $\mathbb{Q}^2$ is <a href="https://cstheory.stackexchange.com/questions/37217/euclidean-tsp-in-np-and-square-root-complexity">not known to be in $\text{P}$, nor even in $\text{NP}$</a>.</p>

<p>Does requiring that the paths begin and end on the same point change anything about our state of knowledge?</p>

<p>What if additionally the paths are not permitted to self-intersect, that is, they are polygons?</p>

<p>Finally, what if the polygons are required to be convex?</p>

<p>My understanding of the obstruction is that the length of a path with $n$ segments is the root of a $2^n$-degree polynomial and we can't rule out that those might end up being so close together that we have to compute exponentially many digits.  Superficially, we're in the same situation with bumpy wheels as with wild scribbles.</p>

CC BY-SA 3.0
2018-03-18T20:32:10.540Z
It should be easy to sort the segments of the path by slope and add extra horizontal and vertical integer-length segments to them so that they both form simple polygons, without changing the comparison.
David Eppstein
CC BY-SA 3.0
2018-03-18T20:58:51.313Z
Okay that makes sense and I feel a little silly now.  I had thought of connecting the endpoints but hadn't considered using two segments (if I'm understanding this right we need up to 3 segments if the $L_1$ distances do not match).  Also this solution is convex so I think that answers everything.
Dan Brumleve
<cc.complexity-theory><tsp>
Complexity of comparing polygon perimeters
Dan Brumleve
# Complexity of comparing polygon perimeters

(Asked by: username_0 on 2018-03-18)

The problem of comparing the lengths of two paths of line segments connecting points in $\mathbb{Q}^2$ is [not known to be in $\text{P}$, nor even in $\text{NP}$](https://cstheory.stackexchange.com/questions/37217/euclidean-tsp-in-np-and-square-root-complexity).

Does requiring that the paths begin and end on the same point change anything about our state of knowledge?

What if additionally the paths are not permitted to self-intersect, that is, they are polygons?

Finally, what if the polygons are required to be convex?

My understanding of the obstruction is that the length of a path with $n$ segments is the root of a $2^n$-degree polynomial and we can't rule out that those might end up being so close together that we have to compute exponentially many digits. Superficially, we're in the same situation with bumpy wheels as with wild scribbles.

**Tags:** cc.complexity-theory, tsp

> **Comments:**
> **username_1**: It should be easy to sort the segments of the path by slope and add extra horizontal and vertical integer-length segments to them so that they both form simple polygons, without changing the comparison.  
> **username_0**: Okay that makes sense and I feel a little silly now.  I had thought of connecting the endpoints but hadn't considered using two segments (if I'm understanding this right we need up to 3 segments if the $L_1$ distances do not match).  Also this solution is convex so I think that answers everything.  

---

## 0 answers

