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

Research paper by **Danny Z. Chen, Rajasekhar Inkulu, Haitao Wang**

Indexed on: **13 Mar '14**Published on: **13 Mar '14**Published in: **Computer Science - Computational Geometry**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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$).