206 citations · 961 across the 151 of their papers we have counts for
186 papers
Overlapping Unfoldings of Cones and Convex Polyhedra
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +4
Research on Dürer's problem focuses on edge unfoldings of convex polyhedra that avoid overlap. We invert the goal and find unfoldings that overlap at some point to any given thickn…
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…