26 citations · 145 across the 52 of their papers we have counts for
11 papers · 1 filter
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, Erik D. Demaine +3
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k…
Minimum Plane Bichromatic Spanning Trees
Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine +3
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endp…
Tiling with Three Polygons is Undecidable
Erik D. Demaine, Stefan Langerman
We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of th…
Deltahedral Domes over Equiangular Polygons
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +6
A polyiamond is a polygon composed of unit equilateral triangles, and a generalized deltahedron is a convex polyhedron whose every face is a convex polyiamond. We study a variant w…
Complexity of 2D Snake Cube Puzzles
MIT Hardness Group, Nithid Anchaleenukoon, Alex Dang +3
Given a chain of cubes where each cube is marked "turn " or "go straight", when can it fold into a rectangular box? We prove several variants o…
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints
NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung +5
We introduce and analyze a model for self-reconfigurable robots made up of unit-cube modules. Compared to past models, our model aims to newly capture two important practical aspec…