# A New Algorithm for Euclidean Shortest Paths in the Plane

Preprint · Haitao Wang

- Archive id: arxiv:2102.12589
- Published: 2021-02-24
- arXiv: https://arxiv.org/abs/2102.12589
- Source URL: https://arxiv.org/abs/2102.12589
- PDF: https://arxiv.org/pdf/2102.12589
- Provenance: arxiv

## Abstract

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri \[SIAM J. Comput. 1999\] gave an algorithm of $O(n\\log n)$ time and $O(n\\log n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri's algorithm, Wang \[SODA 2021\] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(n\\log n)$. In this paper, we present a new algorithm of $O(n+h\\log h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $Ω(n+h\\log h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(\\log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path.

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