Next: Problem 23: Vertex \pi-Floodlights
Previous: Problem 21: Shortest Paths among Obstacles in 2D
Can a minimum-link path among polygonal obstacles be found in subquadratic time?
The best algorithm known requires essentially quadratic time in the worst case [MRW92].
What is the complexity of computing minimum-link paths in three dimensions?
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.