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 (n^10+) \) and queries can be answered in \ (O (n) \) time. Alternatively, we can achieve a space complexity of \ (O (n^9+) \) by relaxing the query time to \ (O (^2n) \). 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^11) \) space complexity and \ (O (n) \) query time. Our main result can be extended to include a space-time trade-off. Specifically, we devise data structures with \ (O (n^9+/ 1. 0pt^4+O () ) \) space complexity and \ (O (^2n) \) 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 (n^6+) \) and the query time \ (O (^2n) \). When both query points are on the boundary, the space complexity is decreased further to \ (O (n^4+) \) and the query time to \ (O (n) \), thereby improving an earlier result of Bae and Okamoto.
Berg et al. (Wed,) studied this question.