1 citations · 2 across the 12 of their papers we have counts for
15 papers
Polyomino Nets Covering Three Different Boxes of Area 106 and Related Results
Erik D. Demaine, Jenny Diomidova, Nicole Jacobus +5
We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three dif…
Who Needs Crossings?: Noncrossing Linkages are Universal, and Deciding (Global) Rigidity is Hard
Zachary Abel, Erik D. Demaine, Martin L. Demaine +3
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid cro…
Undecidability of Tiling with a Tromino
ULB CompGeom Group, Zachary Abel, Hugo Akitaya +6
Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling.…
The Price of Connectivity Augmentation on Planar Graphs
Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5
Given two classes of graphs, , and a -connected graph , we wish to augment with a smallest cardinality set of new e…
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another,…
#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
Max Bannach, Erik D. Demaine, Timothy Gomez +1
The canonical class in the realm of counting complexity is #P. It is well known that the problem of counting the models of a propositional formula in disjunctive normal form (#DNF)…
All Polyhedral Manifolds are Connected by a 2-Step Refolding
Lily Chung, Erik D. Demaine, Jenny Diomidova +4
We prove that, for any two polyhedral manifolds , there is a polyhedral manifold such that share a common unfolding an…
Quasigeodesics on the Cube
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +10
A quasigeodesic is a curve on the surface of a convex polyhedron that has surface to each side at every point. In contrast, a geodesic has exactly to each side and so c…
Continuous Flattening and Reversing of Convex Polyhedral Linkages
Erik D. Demaine, Martin L. Demaine, Markus Hecher +3
We prove two results about transforming any convex polyhedron, modeled as a linkage L of its edges. First, if we subdivide each edge of L in half, then L can be continuously flatte…
Folding One Polyhedral Metric Graph into Another
Lily Chung, Erik D. Demaine, Martin L. Demaine +4
We analyze the problem of folding one polyhedron, viewed as a metric graph of its edges, into the shape of another, similar to 1D origami. We find such foldings between all pairs o…
Dudeney's Dissection is Optimal
Erik D. Demaine, Tonan Kamata, Ryuhei Uehara
In 1907, Henry Ernest Dudeney posed a puzzle: ``cut any equilateral triangle \dots\ into as few pieces as possible that will fit together and form a perfect square'' (without overl…
All Polyhedral Manifolds are Connected by a 2-Step Refolding
Lily Chung, Erik D. Demaine, Jenny Diomidova +4
We prove that, for any two polyhedral manifolds , there is a polyhedral manifold such that share a common unfolding and…
Graph Threading with Turn Costs
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
How should we thread a single string through a set of tubes so that pulling the string taut self-assembles the tubes into a desired graph? While prior work [ITCS 2024] solves this…
Graph Threading
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
Inspired by artistic practices such as beadwork and himmeli, we study the problem of threading a single string through a set of tubes, so that pulling the string forms a desired gr…
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
Hugo A. Akitaya, Erik D. Demaine, Matias Korman +6
A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves…