Subquadratic minimum-link paths among planar obstacles
Among polygonal obstacles in the plane with $n$ vertices in total, a minimum-link path between two points is an obstacle-avoiding polygonal path between them made of as few segments (links) as possible.
The best known algorithm, due to Mitchell, Rote and Woeginger, runs in essentially quadratic worst-case time. A related question concerns how hard minimum-link paths are to compute in three dimensions.
Problem. For polygonal obstacles in the plane with $n$ vertices in total, is there an algorithm that finds a minimum-link path in time subquadratic in $n$?
Source: Origin uncertain, possibly Mitchell; Problem 22 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Keywords
- link distance, minimum-link path, The Open Problems Project
References
@article{mitchellrotewoeginger1992,
author = {Mitchell, Joseph S. B. and Rote, G{\"u}nter and Woeginger, G.},
title = {Minimum-link paths among obstacles in the plane},
journal = {Algorithmica},
volume = {8},
year = {1992},
pages = {431--459},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01076, "Subquadratic minimum-link paths among planar obstacles", clopen.solutions.