Next: Problem 23: Vertex π-Floodlights
Up: The Open Problems Project
Previous: Problem 21: Shortest Paths
Problem 22: Minimum-Link Path in 2D
- Statement
- Can a minimum-link path among polygonal obstacles
be found in subquadratic time?
- Origin
- Mitchell [?].
- Status/Conjectures
- Open.
- Partial and Related Results
- The best algorithm known requires essentially
quadratic time in
the worst case [MRW92].
- Related Open Problems
- What is the complexity of
computing minimum-link paths in three dimensions?
- Appearances
- [MO01]
- Categories
- shortest paths
- Entry Revision History
- J. O'Rourke, 2 Aug. 2001.
- 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.
- MRW92
-
Joseph S. B. Mitchell, Günter Rote, and G. Woeginger.
Minimum-link paths among obstacles in the plane.
Algorithmica, 8:431-459, 1992.
The Open Problems Project - December 08, 2012