Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain

We devise a data structure that can answer shortest path queries for two query points in a polygonal domain \(P\) on \(n\) vertices. For any \(ε>0\) , the space complexity of the data structure is \(O(n10+ε)\) and queries can be answered in \(O(log n)\) time. Alternatively, we can achieve a space complexity of \(O(n9+ε)\) by relaxing the query time to \(O(log²n)\) . This is the first improvement upon a conference paper by Chiang and Mitchell Chiang and Mitchell, [1999] from 1999. They present a data structure with \(O(n¹¹)\) space complexity and \(O(log n)\) query time. Our main result can be extended to include a space-time trade-off. Specifically, we devise data structures with \(O(n9+ε/ 1.0pt4+O(ε))\) space complexity and \(O(log²n)\) query time, for any integer \(1≤≤ n\) . Furthermore, we present improved data structures for the special case where we restrict one (or both) of the query points to lie on the boundary of \(P\) . When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes \(O(n6+ε)\) and the query time \(O(log²n)\) . When both query points are on the boundary, the space complexity is decreased further to \(O(n4+ε)\) and the query time to \(O(log n)\) , thereby improving an earlier result of Bae and Okamoto.