Strong NP-hardness of moving many discs

DOI10.1016/0020-0190(84)90130-3zbMath0539.68037OpenAlexW2068796584MaRDI QIDQ794168

Chee-Keng Yap, Paul G. Spirakis

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90130-3

zbMATH Keywords

partitionNP-complete problemsreductionsmotion planningroboticsmotion coordinationcollision avoidancedisc- packinggeometric avoidance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Artificial intelligence (68T99)

Related Items

Motion planning among time dependent obstacles ⋮ Translation separability of sets of polygons ⋮ On multiple moving objects ⋮ A tight lower bound for the complexity of path-planning for a disc ⋮ A survey of motion planning and related geometric algorithms ⋮ Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch ⋮ Unnamed Item ⋮ Efficient coordinated motion.

Cites Work

• Unnamed Item