4
$\begingroup$

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

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.

| cite | improve this question | |
$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – David Eppstein Mar 18 '18 at 20:32
  • $\begingroup$ 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. $\endgroup$ – Dan Brumleve Mar 18 '18 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.