Next: Problem 23: Vertex πFloodlights
Up: The Open Problems Project
Previous: Problem 21: Shortest Paths
Problem 22: MinimumLink Path in 2D
 Statement
 Can a minimumlink 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 minimumlink 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):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 MRW92

Joseph S. B. Mitchell, Günter Rote, and G. Woeginger.
Minimumlink paths among obstacles in the plane.
Algorithmica, 8:431459, 1992.
The Open Problems Project  September 19, 2017