# Computing L1 Shortest Paths among Polygonal Obstacles in the Plane

Article · Danny Z. Chen, Haitao Wang

- Archive id: arxiv:1202.5715
- Published: 2012-02-26
- Venue: Algorithmica
- DOI: https://doi.org/10.1007/s00453-018-00540-x
- arXiv: https://arxiv.org/abs/1202.5715
- Citations: 10
- Source URL: https://arxiv.org/abs/1202.5715
- PDF: https://arxiv.org/pdf/1202.5715
- Provenance: arxiv

## Abstract

Given a point $s$ and a set of $h$ pairwise disjoint polygonal obstacles of totally $n$ vertices in the plane, we present a new algorithm for building an $L\_1$ shortest path map of size O(n) in $O(T)$ time and O(n) space such that for any query point $t$, the length of the $L\_1$ shortest obstacle-avoiding path from $s$ to $t$ can be reported in $O(\\log n)$ time and the actual shortest path can be found in additional time proportional to the number of edges of the path, where $T$ is the time for triangulating the free space. It is currently known that $T=O(n+h\\log^{1+ε}h)$ for an arbitrarily small constant $ε\>0$. If the triangulation can be done optimally (i.e., $T=O(n+h\\log h)$), then our algorithm is optimal. Previously, the best algorithm computes such an $L\_1$ shortest path map in $O(n\\log n)$ time and O(n) space. Our techniques can be extended to obtain improved results for other related problems, e.g., computing the $L\_1$ geodesic Voronoi diagram for a set of point sites in a polygonal domain, finding shortest paths with fixed orientations, finding approximate Euclidean shortest paths, etc.

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