**Next:** Problem 22: Minimum-Link Path in 2D

**Previous:** Problem 20: Minimum Stabbing Spanning Tree

- Statement
Can shortest paths among h obstacles in the plane, with a total of n vertices, be found in optimal O(n + h \log h) time using O(n) space?

- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

- Partial and Related Results
The only algorithm that is linear in n in time and space is quadratic in h [KMM97]; O(n\log n) time, using O(n\log n) space, is known [HS99]. In three dimensions, the Euclidean shortest path problem among general obstacles is NP-hard, but its complexity remains open for some special cases, such as when the obstacles are disjoint unit spheres or axis-aligned boxes; see [Mit00] for a survey.

- Appearances
- Categories
shortest paths

- Entry Revision History
J. O’Rourke, 2 Aug. 2001.

- [HS99]
John Hershberger and Subhash Suri. An optimal algorithm for Euclidean shortest paths in the plane.

*SIAM J. Comput.*, 28(6):2215–2256, 1999.- [KMM97]
S. Kapoor, S. N. Maheshwari, and Joseph S. B. Mitchell. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane.

*Discrete Comput. Geom.*, 18:377–383, 1997.- [Mit00]
Joseph S. B. Mitchell. Geometric shortest paths and network optimization. In Jörg-Rüdiger Sack and Jorge Urrutia, editors,

*Handbook of Computational Geometry*, pages 633–701. Elsevier Publishers B.V. North-Holland, Amsterdam, 2000.- [MO01]
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42.

*Internat. J. Comput. Geom. Appl.*, 11(5):573–582, 2001. Also in*SIGACT News*32(3):63-72 (2001), Issue 120.