Pushing blocks is hard.

DOI10.1016/S0925-7721(02)00170-0zbMath1041.65021OpenAlexW1999708036MaRDI QIDQ1395573

D. Massart

Publication date: 1 July 2003

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(02)00170-0

zbMATH Keywords

computational complexityNP-hardmotion planningcomputational geometrycombinatorial gamesrobotEulerian tours of planar graphspush-X open problem

Mathematics Subject Classification ID

Games involving graphs (91A43) Kinematics of mechanisms and robots (70B15) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items (8)

\textsc{Pull} and \textsc{PushPull} are PSPACE-complete ⋮ Unnamed Item ⋮ Hybrid planning for challenging construction problems: an answer set programming approach ⋮ Unnamed Item ⋮ CADbots: algorithmic aspects of manipulating programmable matter with finite automata ⋮ The snowblower problem ⋮ Forming tile shapes with simple robots ⋮ The computational complexity of Angry Birds

Cites Work

• Parallel concepts in graph theory
• Motion planning in the presence of movable obstacles
• SOKOBAN and other motion planning problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pushing blocks is hard.