# Shortest Paths Among Obstacles in the Plane Revisited

Article · Haitao Wang

- Archive id: arxiv:2010.09115
- Published: 2020-10-18
- Venue: Society for Industrial and Applied Mathematics eBooks
- DOI: https://doi.org/10.1137/1.9781611976465.51
- arXiv: https://arxiv.org/abs/2010.09115
- Citations: 11
- Source URL: https://arxiv.org/abs/2010.09115
- PDF: https://arxiv.org/pdf/2010.09115
- 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. The previous best algorithm was given by Hershberger and Suri \[FOCS 1993, SIAM J. Comput. 1999\] and the algorithm runs in $O(n\\log n)$ time and $O(n\\log n)$ space, where $n$ is the total number of vertices of all obstacles. The algorithm is time-optimal because $Ω(n\\log n)$ is a lower bound. It has been an open problem for over two decades whether the space can be reduced to $O(n)$. In this paper, we settle it by solving the problem in $O(n\\log n)$ time and $O(n)$ space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point $s$ in $O(n\\log n)$ time and $O(n)$ space, such that given any query point $t$, the length of a shortest path from $s$ to $t$ can be computed in $O(\\log n)$ time and a shortest 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)._

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.