Optimal shortest path queries in a simple polygon

摘要

Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P, the length of the shortest path inside the polygon from p to q can be found in time O(log n). The path itself must be polygonal and can be extracted in additional time proportional to the number of turns it makes. The preprocessing consists of triangulation plus a linear amount of additional work.