Next: Problem 23: Vertex π-Floodlights
Up: The Open Problems Project
Previous: Problem 21: Shortest Paths
Problem 22: Minimum-Link Path in 2D
- Can a minimum-link path among polygonal obstacles
be found in subquadratic time?
- Mitchell [?].
- 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?
- shortest paths
- Entry Revision History
- J. O'Rourke, 2 Aug. 2001.
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.
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 04, 2015