The Open Problems Project

Next: Problem 23: Vertex \pi-Floodlights

Previous: Problem 21: Shortest Paths among Obstacles in 2D

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.