26 citations · 145 across the 48 of their papers we have counts for
11 papers · 1 filter
Characterizing Universal Reconfigurability of Modular Pivoting Robots
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi +7
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we co…
Arithmetic Expression Construction
Leo Alcock, Sualeh Asif, Jeffrey Bosboom +10
When can given numbers be combined using arithmetic operators from a given subset of to obtain a given target number? We study three variations of this pr…
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
Josh Brunner, Erik D. Demaine, Dylan Hendrickson +1
We prove PSPACE-completeness of two classic types of Chess problems when generalized to n-by-n boards. A "retrograde" problem asks whether it is possible for a position to be reach…
Tetris is NP-hard even with rows or columns
Sualeh Asif, Michael Coulombe, Erik D. Demaine +4
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
Erik D. Demaine, Martin L. Demaine, David Eppstein
We present new examples of topologically convex edge-ununfoldable polyhedra, i.e., polyhedra that are combinatorially equivalent to convex polyhedra, yet cannot be cut along their…
Negative Instance for the Edge Patrolling Beacon Problem
Zachary Abel, Hugo A. Akitaya, Erik D. Demaine +5
Can an infinite-strength magnetic beacon always ``catch'' an iron ball, when the beacon is a point required to be remain nonstrictly outside a polygon, and the ball is a point alwa…