Optimal shortest path queries in a simple polygon (Q1823689)

The paper focuses on a simple version of the Euclidean shortest path problem: moving a point inside a simple polygon with n sides. It shows how to preprocess the polygon P so that, given two query points p and q inside the polygon, the Euclidean length of the shortest path inside P from p to q can be found in sublinear time 0(log n). The path itself must be polygonal. The paper gives a data structure that supports such shortest path queries when both endpoints are part of the query. The preprocessing phase gives a hierarchy of nested subpolygons over an underlying triangulation, such that any shortest path crosses a small number of subpolygons only. So preprocessing consists of triangulation plus a linear amount of additional work. Interesting applications and extensions are discussed at the end of the paper (disk moving, relative convex hulls).