Shortest path in polygonal domain

Question

The single shot query for the shortest path between two points in a plane environment with polygonal obstacles of complexity $O(n)$ can be solved in time $O(n \log n)$ using the continuous Dijkstra method.

What happens if I am given a set $P$ of $k$ points in the plane, and I want to preprocess them, s.t. the shortest path between any two points in $P$ can be computed efficiently. Are there any algorithms known for this problem?

Thank you

Stefan

Answer 1

The paper by Chiang and Mitchell, "Two-Point Euclidean Shortest Path Queries in the Plane" (1999), might answer your question:

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 ... of an Euclidean shortest obstacle-avoiding path ... from $s$ to $t$. ... 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^2 n)$ or optimal $O(\log n)$ query times, using polynomial-space data structures, with various tradeoffs between space and query time.

In your case (points rather than polygonal obstacles), $h=n$.