A tight lower bound for the complexity of path-planning for a disc

DOI10.1016/0020-0190(88)90203-7zbMath0657.68115OpenAlexW2077643376MaRDI QIDQ1111039

Colm P. O'Dunlaing

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90203-7

zbMATH Keywords

motion planningcomputational geometryalgebraic decision tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Related Items (3)

Minimum-link paths among obstacles in the plane ⋮ Moving a disc between polygons ⋮ Decision trees: Old and new results.

Cites Work

• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• Strong NP-hardness of moving many discs
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• A “retraction” method for planning the motion of a disc
• Movement Problems for 2-Dimensional Linkages

This page was built for publication: A tight lower bound for the complexity of path-planning for a disc