Next: Problem 22: MinimumLink Path
Up: The Open Problems Project
Previous: Problem 20: Minimum Stabbing
Problem 21: Shortest Paths among Obstacles in 2D
 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 NPhard, but its complexity remains open
for some special cases, such as when the obstacles are disjoint unit
spheres or axisaligned boxes; see [Mit00] for a survey.
 Appearances
 [MO01]
 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):22152256, 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:377383, 1997.
 Mit00

Joseph S. B. Mitchell.
Geometric shortest paths and network optimization.
In JörgRüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 633701. Elsevier Publishers B.V.
NorthHolland, Amsterdam, 2000.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
The Open Problems Project  December 04, 2015