52 citations · 271 across the 48 of their papers we have counts for
40 papers · 1 filter
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…
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…
Orthogonal Fold & Cut
Hayashi Ani, Josh Brunner, Erik D. Demaine +4
We characterize the cut patterns that can be produced by "orthogonal fold & cut": folding an axis-aligned rectangular sheet of paper along horizontal and vertical creases, and then…
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings
Erik D. Demaine, Martin L. Demaine, Jenny Diomidova +3
We show that several classes of polyhedra are joined by a sequence of O(1) refolding steps, where each refolding step unfolds the current polyhedron (allowing cuts anywhere on the…
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
Zachary Abel, Erik D. Demaine, Martin L. Demaine +4
We prove that any finite polyhedral manifold in 3D can be continuously flattened into 2D while preserving intrinsic distances and avoiding crossings, answering a 19-year-old open p…
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…
Escaping a Polygon
Zachary Abel, Hugo Akitaya, Erik D. Demaine +4
Suppose an escaping player ("human") moves continuously at maximum speed in the interior of a region, while a pursuing player ("zombie") moves continuously at maximum speed …
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…
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
Existence and hardness of conveyor belts
Molly Baird, Sara C. Billey, Erik D. Demaine +7
An open problem of Manuel Abellanas asks whether every set of disjoint closed unit disks in the plane can be connected by a conveyor belt, which means a tight simple closed curve t…
Some Polycubes Have No Edge Zipper Unfolding
Erik D. Demaine, Martin L. Demaine, David Eppstein +1
It is unknown whether every polycube (polyhedron constructed by gluing cubes face-to-face) has an edge unfolding, that is, cuts along edges of the cubes that unfolds the polycube t…
Conic Crease Patterns with Reflecting Rule Lines
Erik D. Demaine, Martin L. Demaine, David A. Huffman +2
We characterize when two conic curved creases are compatible with each other, when the rule lines must converge to conic foci and reflect at the crease. Namely, two conics are comp…
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3
We prove that path puzzles with complete row and column information--or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint--are strongly NP-complete, ASP…
Folding Polyominoes into (Poly)Cubes
Oswin Aichholzer, Michael Biro, Erik D. Demaine +6
We study the problem of folding a polyomino into a polycube , allowing faces of to be covered multiple times. First, we define a variety of folding models according to w…
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron
Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine +1
We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid--for example, the surface of…
Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces
Cameron Chalk, Erik D. Demaine, Martin L. Demaine +4
We show how to design a universal shape replicator in a self-assembly system with both attractive and repulsive forces. More precisely, we show that there is a universal set of con…
Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +4
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1…
Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations
Erik D. Demaine, Martin L. Demaine, David A. Huffman +2
We describe a general family of curved-crease folding tessellations consisting of a repeating "lens" motif formed by two convex curved arcs. The third author invented the first suc…
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
Zachary Abel, Erik D. Demaine, Martin L. Demaine +3
When can a plane graph with prescribed edge lengths and prescribed angles (from among \}) be folded flat to lie in an infinitesimally thin line, without c…
Covering Folded Shapes
Oswin Aichholzer, Greg Aloupis, Erik D. Demaine +6
Can folding a piece of paper flat make it larger? We explore whether a shape must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary f…
Fun with Fonts: Algorithmic Typography
Erik D. Demaine, Martin L. Demaine
Over the past decade, we have designed six typefaces based on mathematical theorems and open problems, specifically computational geometry. These typefaces expose the general publi…
Covering Points by Disjoint Boxes with Outliers
Hee-Kap Ahn, Sang Won Bae, Erik D. Demaine +5
For a set of n points in the plane, we consider the axis--aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this…
A Universal Crease Pattern for Folding Orthogonal Shapes
Nadia Benbernou, Erik D. Demaine, Martin L. Demaine +1
We present a universal crease pattern--known in geometry as the tetrakis tiling and in origami as box pleating--that can fold into any object made up of unit cubes joined face-to-f…