next up previous
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.

Bibliography

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 04, 2015