22
$\begingroup$

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path from $s$ to $t$ that does not intersect the interior of any polygon. For concreteness, let us assume that the coordinates of $s$ and $t$, and the coordinates of every polygon vertex, are integers.

Can this problem be solved in polynomial time?

Most computational geometers would immediately say yes, of course: John Hershberger and Subhash Suri described an algorithm that computes Euclidean shortest paths in $O(n\log n)$ time, and this time bound is optimal in the algebraic computational tree model. Unfortunately, Hershberger and Suri's algorithm (and nearly all related algorithms before and since) seems to require exact real arithmetic in the following strong sense.

Call a polygonal path valid if all its interior vertices are obstacle vertices; every Euclidean shortest path is valid. The length of any valid path is the sum of square roots of integers. Thus, comparing the lengths of two valid paths requires comparing two sums of square roots, which we don't know how to do in polynomial time.

Moreover, it seems completely plausible that an arbitrary instance of the sum-of-square-roots problem could be reduced to an equivalent Euclidean shortest-path problem.

So: Is there a polynomial-time algorithm to compute Euclidean shortest paths? Or is the problem NP-hard? Or sum-of-square-roots-hard? Or something else?

A few notes:

  • Shortest paths inside (or outside) one polygon can be computed in $O(n)$ time without any strange numerical issues using the standard funnel algorithm, at least if a triangulation of the polygon is given.

  • In practice, floating-point arithmetic is sufficient to compute paths that are shortest up to floating-point precision. I'm only interested in the complexity of the exact problem.

  • John Canny and John Reif proved that the corresponding problem in 3-space is NP-hard (morally because there may be an exponential number of shortest paths). Joonsoo Choi, Jürgen Sellen, and Chee-Keng Yap described a polynomial-time approximation scheme.

  • Simon Kahan and Jack Snoeyink considered similar issues for the related problem of minimum-link paths in a simple polygon.

$\endgroup$
  • 4
    $\begingroup$ it would be nice if there were a list of sum-of-square-roots hard problems. $\endgroup$ – Suresh Venkat Dec 31 '10 at 18:41
  • 4
    $\begingroup$ This sounds like a perfect question for cstheory. Why don't you ask it? $\endgroup$ – Peter Shor Jan 1 '11 at 14:31
  • 2
    $\begingroup$ Done: cstheory.stackexchange.com/questions/4053/… $\endgroup$ – Jeffε Jan 12 '11 at 18:50
4
$\begingroup$

Maybe I miss something, but if we consider the "easy" case, where all obstacles are points, then we have the problem of computing the shortest path between two vertices in a planar graph, which, if I am not wrong, it is known as sums-of-square-roots-hard.

PS. I wanted to add a comment and not an answer, but I can't find how. I apologize for that. Can the admins please help me with this.

$\endgroup$
  • $\begingroup$ You need 50 reputation to post a comment in stackexchange. More details here: cstheory.stackexchange.com/privileges/comment . Since you are providing some information, I guess it's ok to post it as an answer. $\endgroup$ – chazisop Dec 31 '10 at 10:45
  • 1
    $\begingroup$ In the "easy" case where the obstacles are points, the Euclidean shortest path (or more formally, the infimal path) is always a straight line segment, and computing it is trivial. But even for shortest paths in planar graphs with Euclidean edge lengths, do you have a reference for sum-of-roots hardness? (It's not hard to see a reduction for four-dimensional graphs, because every integer is the sum of at most four perfect squares.) $\endgroup$ – Jeffε Jan 1 '11 at 6:20
  • 3
    $\begingroup$ So in the plane, this will reduce to the sum of square roots of integers which are the products of squares and primes of the form $4k+1$? I don't think I've ever seen any reference to this problem before, but it's now obvious that it's quite relevant for computational geometry. Maybe you should put this observation in your question. $\endgroup$ – Peter Shor Jan 1 '11 at 14:35
  • $\begingroup$ You are right. The "easy" case is rather a trivial one. $\endgroup$ – Elias Jan 2 '11 at 10:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.