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

Abstract

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(log2 n). This is the first improvement upon a conference paper by Chiang and Mitchell from 1999. They presented a data structure with O(n11) 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+ε/ℓ4+O(ε)) space complexity and O(ℓlog2 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(log2 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.