Two-point L1 shortest path queries in the plane

Abstract

Let $P$ be a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices in the plane. We consider the problem of building a data structure that can quickly compute an $L_1$ shortest obstacle-avoiding path between any two query points $s$ and $t$. Previously, a data structure of size $O(n^2\log n)$ was constructed in $O(n^2\log^2 n)$ time that answers each two-point query in $O(\log^2 n+k)$ time, i.e., the shortest path length is reported in $O(\log^2 n)$ time and an actual path is reported in additional $O(k)$ time, where $k$ is the number of edges of the output path. In this paper, we build a new data structure of size $O(n+h^2 \log h 4^{\sqrt{\log h}})$ in $O(n+h^2 \log^{2}h 4^{\sqrt{\log h}})$ time that answers each query in $O(\log n+k)$ time. (In contrast, for the Euclidean version of this two-point query problem, the best known algorithm uses $O(n^{11})$ space to achieve an $O(\log n+k)$ query time.) Further, we extend our techniques to the weighted rectilinear version in which the ``obstacles" of $P$ are rectilinear regions with ``weights" and allow $L_1$ paths to travel through them with weighted costs. Previously, a data structure of size $O(n^2\log^2 n)$ was built in $O(n^2\log^2 n)$ time that answers each query in $O(\log^2 n+k)$ time. Our new algorithm answers each query in $O(\log n+k)$ time with a data structure of size $O(n^2 \log n 4^{\sqrt{\log n}})$ that is built in $O(n^2 \log^2 n 4^{\sqrt{\log n}})$ time.