# Shortest path in polygonal domain

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

-
It is a slightly strange question, as the shortest path is just the straight segment between any pair of points. But, nevertheless, the reference I cite below may be useful. – Joseph O'Rourke Dec 25 '11 at 15:57
So the question is really about $k$ points in a planar scene with polygonal obstacles? – Louis Dec 25 '11 at 18:39
Yes, sorry about the confusion, I've edited the original post since I wrongly used the word polygonal domain to describe a planar scene with polygonal obstacles – stefan Dec 25 '11 at 18:45
Hm, but I am still not sure about the exact definition of polygonal domain. – stefan Dec 25 '11 at 21:59

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$.