Two-Point $L_1$ Shortest Path Queries in the Plane

Abstract

Let $\mathcal{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\cdot \log h\cdot 4^{\sqrt{\log h}})$ in $O(n+h^2\cdot {\log }^{2}h\cdot 4^{\sqrt{\log h}})$ time that answers each query in $O(\log n+k)$ time. Note that $n+h^2\cdot {\log }^{2}h\cdot 4^{\sqrt{\log h}}=O(n+h^{2+\epsilon })$ for any constant $\epsilon >0$. Further, we extend our techniques to the weighted rectilinear version in which the "obstacles" of $\mathcal{P}$ are rectilinear regions with "weights" and allow $L_1$ paths to travel through them with weighted costs. Our algorithm answers each query in $O(\log n+k)$ time with a data structure of size $O(n^2\cdot \log n\cdot 4^{\sqrt{\log n}})$ that is built in $O(n^2\cdot {\log }^{2}n\cdot 4^{\sqrt{\log n}})$ time (note that $n^2\cdot {\log }^{2}n\cdot 4^{\sqrt{\log n}}=O(n^{2+\epsilon })$ for any constant $\epsilon >0$).

38 pages, 13 figures. A preliminary version appeared in SoCG 2014

References in corpus (2)

• A near optimal algorithm for finding Euclidean shortest path in polygonal domain
• Computing L1 Shortest Paths among Polygonal Obstacles in the Plane

Cited by in corpus (1)

• An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains