Pushing blocks is hard.

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

D. Massart

Publication date: 1 July 2003

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

zbMATH Keywords

computational complexity; NP-hard; motion planning; computational geometry; combinatorial games; robot; Eulerian tours of planar graphs; push-X open problem

Mathematics Subject Classification ID

91A43: Games involving graphs

70B15: Kinematics of mechanisms and robots

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

65Y20: Complexity and performance of numerical algorithms