Two-point Euclidean shortest path queries in the plane

We consider the two-point query version of the fundamental geometric shortest path problem: Given a set h of polygonal obstacles in the plane, having a total of n vertices, build a data structure such that for any two query points s and t we can efficiently determine the length, d(s,t), of an Euclidean shortest obstacle-avoiding path, π(s, t), from s to t. Additionally, our data structure should allow one to report the path π(s, t), in time proportional to its (combinatorial) size. We present various methods for solving this two-point query problem, including algorithms with o(n), O(log n+h), O(h log n), O(log² n) or optimal O(log n) query times, using polynomial-space data structures, with various tradeoffs between space and query time. While several results have been known for approximate two-point Euclidean shortest path queries, it has been a well-publicized open problem to obtain sublinear query time for the exact version of the problem. Our methods also yield data structures for two-point shortest path queries on nonconvex polyhedral surfaces.