We consider shortest path queries in a polygonal domain P having n vertices and h holes. A skeleton graph is a subgraph of a Voronoi diagram of P. Our novel algorithm utilizes a reduced skeleton graph of P to compute a tessellation of P. It builds a data structure of size O(n 2) in O(n 2logn) time to support distance queries for any pair of query points in P in O(hlogn) time.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-540-68880-8_20
Guo, H. (Hua), Maheshwari, A, & Sack, J.-R. (2008). Shortest path queries in polygonal domains. doi:10.1007/978-3-540-68880-8_20