Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.