Next: Problem 22: Minimum-Link Path
Up: The Open Problems Project
Previous: Problem 20: Minimum Stabbing
Problem 21: Shortest Paths among Obstacles in 2D
- Can shortest paths among h obstacles in the plane,
with a total of n vertices, be found in
O(n + h log h) time using O(n) space?
- Uncertain, pending investigation.
- 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.
- shortest paths
- Entry Revision History
- J. O'Rourke, 2 Aug. 2001.
John Hershberger and Subhash Suri.
An optimal algorithm for Euclidean shortest paths in the plane.
SIAM J. Comput., 28(6):2215-2256, 1999.
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.
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.
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.
The Open Problems Project - December 04, 2015