**Next:** Problem 23: Vertex \pi-Floodlights

**Previous:** Problem 21: Shortest Paths among Obstacles 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
- 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.