Shortest paths among obstacles in the plane

We give a subquadratic (O(n^3/2+c) time and O(n) space) algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles; previous time bounds were at least quadratic in n, in the worst case. The method avoids use of visibility graphs, relying instead on the continuous Dijkstra paradigm. The output is a shortest path map (of size O(n)) with respect to a given source point, which allows shortest path length queries to be answered in tune O(log n). The algorithm extends to the case of multiple source points, yielding a method to compute a Voronoi diagram with respect to the shortest path metric.