# $L_1$ Shortest Path Queries in Simple Polygons

Article · Sang Won Bae, Haitao Wang

- Archive id: arxiv:1809.07481
- Published: 2018-09-20
- Venue: Theoretical Computer Science
- DOI: https://doi.org/10.1016/j.tcs.2019.04.023
- arXiv: https://arxiv.org/abs/1809.07481
- Citations: 4
- Source URL: https://arxiv.org/abs/1809.07481
- PDF: https://arxiv.org/pdf/1809.07481
- Provenance: arxiv

## Abstract

Let $P$ be a simple polygon of $n$ vertices. We consider two-point $L\_1$ shortest path queries in $P$. We build a data structure of $O(n)$ size in $O(n)$ time such that given any two query points $s$ and $t$, the length of an $L\_1$ shortest path from $s$ to $t$ in $P$ can be computed in $O(\\log n)$ time, or in $O(1)$ time if both $s$ and $t$ are vertices of $P$, and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

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