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

Preprint · Danny Z. Chen, Rajasekhar Inkulu, Haitao Wang

- Archive id: arxiv:1403.3458
- Published: 2014-03-13
- arXiv: https://arxiv.org/abs/1403.3458
- Source URL: https://arxiv.org/abs/1403.3458
- PDF: https://arxiv.org/pdf/1403.3458
- Provenance: arxiv

## 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+ε})$ for any constant $ε\>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+ε})$ for any constant $ε\>0$).

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.