<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-31T10:45:42.237Z
You need 50 reputation to post a comment in stackexchange. More details here: http://cstheory.stackexchange.com/privileges/comment . Since you are providing some information, I guess it's ok to post it as an answer.
chazisop
CC BY-SA 2.5
2011-01-01T06:20:13.877Z
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.)
Jeffε
CC BY-SA 2.5
2011-01-01T14:35:24.803Z
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.
Peter Shor 
CC BY-SA 2.5
2011-01-02T10:24:39.970Z
You are right. The "easy" case is rather a trivial one.
Elias
CC BY-SA 2.5
2010-12-31T10:23:30.977Z
2010-12-31T12:03:01.290Z
2010-12-31T12:03:01.290Z
Elias
<p>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.</p>

<p><strong>Can this problem be solved in polynomial time?</strong></p>

<p>Most computational geometers would immediately say yes, of course: <a href="http://dx.doi.org/10.1137/S0097539795289604" rel="nofollow noreferrer">John Hershberger and Subhash Suri</a> 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 <em>require</em> exact real arithmetic in the following strong sense.</p>

<p>Call a polygonal path <em>valid</em> 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, <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010"><em>which we don't know how to do in polynomial time</em></a>.</p>

<p>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.</p>

<p>So: <strong>Is there a polynomial-time algorithm to compute Euclidean shortest paths?  Or is the problem NP-hard?  Or <a href="https://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems">sum-of-square-roots-hard</a>?  Or something else?</strong></p>

<p>A few notes:</p>

<ul>
<li><p>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.</p></li>
<li><p>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 <em>exact</em> problem.</p></li>
<li><p><a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1987.42" rel="nofollow noreferrer">John Canny and John Reif</a> proved that the corresponding problem in 3-space is NP-hard (morally because there may be an exponential number of shortest paths).  <a href="http://portal.acm.org/citation.cfm?id=177501" rel="nofollow noreferrer">Joonsoo Choi, Jürgen Sellen, and Chee-Keng Yap</a> described a polynomial-time approximation scheme.</p></li>
<li><p><a href="http://dx.doi.org/10.1016/S0925-7721(98)00041-8" rel="nofollow noreferrer">Simon Kahan and Jack Snoeyink</a> considered similar issues for the related problem of minimum-link paths in a simple polygon.</p></li>
</ul>

CC BY-SA 2.5
2010-12-31T18:41:53.513Z
it would be nice if there were a list of sum-of-square-roots hard problems.
Suresh Venkat
CC BY-SA 2.5
2011-01-01T14:31:58.703Z
This sounds like a perfect question for cstheory. Why don't you ask it?
Peter Shor 
CC BY-SA 2.5
2011-01-12T18:50:24.020Z
Done: http://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems
Jeffε
<ds.algorithms><cg.comp-geom><open-problem><computing-over-reals>
Complexity of computing shortest paths in the plane with polygonal obstacles
Jeffε
# Complexity of computing shortest paths in the plane with polygonal obstacles

(Asked by: username_0 on 2010-12-31)

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](http://dx.doi.org/10.1137/S0097539795289604) 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*](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010).

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](https://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems)? 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](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1987.42) 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](http://portal.acm.org/citation.cfm?id=177501) described a polynomial-time approximation scheme.
* [Simon Kahan and Jack Snoeyink](http://dx.doi.org/10.1016/S0925-7721(98)00041-8) considered similar issues for the related problem of minimum-link paths in a simple polygon.

**Tags:** ds.algorithms, cg.comp-geom, open-problem, computing-over-reals
> **Comments:**
> **username_1**: it would be nice if there were a list of sum-of-square-roots hard problems.  
> **username_2**: This sounds like a perfect question for cstheory. Why don't you ask it?  
> **username_0**: Done: http://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems  

---

## 1 answers

### Answer by username_3 on 2010-12-31. Score: 4

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.

> **Comments:**
> **username_4**: You need 50 reputation to post a comment in stackexchange. More details here: http://cstheory.stackexchange.com/privileges/comment . Since you are providing some information, I guess it's ok to post it as an answer.  
> **username_0**: 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.)  
> **username_2**: 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.  
> **username_3**: You are right. The "easy" case is rather a trivial one.  

---

