11 papers
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,…
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…
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…
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…
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…