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

Preprint · Haitao Wang

- Archive id: arxiv:1903.01417
- Published: 2019-03-04
- arXiv: https://arxiv.org/abs/1903.01417
- Source URL: https://arxiv.org/abs/1903.01417
- PDF: https://arxiv.org/pdf/1903.01417
- Provenance: arxiv

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