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 $\varepsilon > 0$, the space complexity of the data structure is $O(n^{10+\varepsilon})$ and queries can be answered in $O(\log n)$ time. This is the first improvement upon a conference paper by Chiang and Mitchell from 1999. They present a data structure with $O(n^{11})$ space complexity. Our main result can be extended to include a space-time trade-off. Specifically, we devise data structures with $O(n^{10+\varepsilon}/\hspace{1pt} \ell^{5 + O(\varepsilon)})$ space complexity and $O(\ell \log n )$ query time for any integer $1 \leq \ell \leq n$. Furthermore, our main result can be improved if 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 can still lie anywhere in $P$, the space complexity becomes $O(n^{6+\varepsilon})$. When both query points are on the boundary, the space is decreased further to $O(n^{4+\varepsilon})$, thereby improving an earlier result of Bae and Okamoto.