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.
