A Divide-and-Conquer Algorithm for Two-Point $L_1$ Shortest Path Queries in Polygonal Domains

Abstract

Let $\mathcal{P}$ be a polygonal domain of $h$ holes and $n$ vertices. We study the problem of constructing a data structure that can compute a shortest path between $s$ and $t$ in $\mathcal{P}$ under the $L_1$ metric for any two query points $s$ and $t$. To do so, a standard approach is to first find a set of $n_s$ "gateways" for $s$ and a set of $n_t$ "gateways" for $t$ such that there exist a shortest $s$-$t$ path containing a gateway of $s$ and a gateway of $t$, and then compute a shortest $s$-$t$ path using these gateways. Previous algorithms all take quadratic $O(n_s\cdot n_t)$ time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in $O(n_s + n_t \log n_s)$ time. As a consequence, we construct a data structure of $O(n+(h^2\log^3 h/\log\log h))$ size in $O(n+(h^2\log^4 h/\log\log h))$ time such that each query can be answered in $O(\log n)$ time.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.