Covering Points by Disjoint Boxes with Outliers (2009)
Ahn, Hee-Kap, Bae, Sang Won, Demaine, Erik D., Demaine, Martin L., Kim, Sang-Sub, Korman, Matias, ...
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 paper, we consider...
A Universal Crease Pattern for Folding Orthogonal Shapes (2009)
Benbernou, Nadia, Demaine, Erik D., Demaine, Martin L., Ovadya, Aviv
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-face (polycubes)....
Minimum feature size preserving decompositions (2009)
Aloupis, Greg, Demaine, Erik D., Demaine, Martin L., Dujmovic, Vida, Iacono, John
The minimum feature size of a crossing-free straight line drawing is the minimum distance between a vertex and a non-incident edge. This quantity measures the resolution needed to display a figure or...
(Non)existence of Pleated Folds: How Paper Folds Between Creases (2009)
Demaine, Erik D., Demaine, Martin L., Hart, Vi, Price, Gregory N., Tachi, Tomohiro
We prove that the pleated hyperbolic paraboloid, a familiar origami model known since 1927, in fact cannot be folded with the standard crease pattern in the standard mathematical model of...
Continuous Blooming of Convex Polyhedra (2009)
Demaine, Erik D., Demaine, Martin L., Hart, Vi, Iacono, John, Langerman, Stefan, O'Rourke, Joseph
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further...
PUZZLES, ART, AND MAGIC WITH ALGORITHMS (2008)
Erik D. Demaine, Martin L. Demaine
Solving and designing puzzles, creating sculpture and architecture, and inventing magic tricks all lead to fun and interesting algorithmic problems. This paper describes some of our explorations into...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Planar Drawings of Origami Polyhedra (2008)
Erik D. Demaine, Martin L. Demaine
Abstract We present a new infinite class of polyhedra based on a class of origami bases that we have developed. To understand these polyhedra and their underlying bases, we examine drawings of their...
Polygons Cuttable by a Circular Saw Erik D. Demaine \Lambda (2008)
Martin L. Demaine, Craig S. Kaplan
y
Sliding-coin Puzzles, Erik D. Demaine, Martin L. Demaine
The rest of this section presents several sliding-coin puzzles. 1.1 Triangular Lattice We start with some basic puzzles that are on the triangular lattice in the sense that the center of every coin...
Erik D. Demaine, Martin L. Demaine, Perouz Taslakian, Godfried T. Toussaint
Sand drawings form a part of many cultural artistic traditions. Depending on the part of the world in which they occur, such drawings have different names such as sona, kolam, and Malekula drawings....
Abstract Wrapping the Mozartkugel (2008)
Erik D. Demaine, Martin L. Demaine, John Iacono, Stefan Langerman
We study wrappings of the unit sphere by a piece of paper (or, perhaps more accurately, a piece of foil). Such wrappings differ from standard origami because they require infinitely many...
Abstract Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2008)
Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, ...
We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two nonoverlapping convex polygons in the plane. Given two non-overlapping convex polygons P1 and P2 in the...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
The field of ethnomathematics is the study of mathematics in the works of art of various cultures [2, 3, 9, 13]. The concepts
Cauchy's Arm Lemma on a Growing Sphere (2008)
Abel, Zachary, Charlton, David, Collette, Sebastien, Demaine, Erik D., Demaine, Martin L., Langerman, Stefan, ...
We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases....
Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity ∗ (2008)
Erik D. Demaine, Martin L. Demaine
Abstract. We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles are all NP-complete. Furthermore, we show direct equivalences between these three types of puzzles: any...
Abstract Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane (2008)
Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, ...
We provide an efficient data structure for dynamically maintaining a ham-sandwich cut of two nonoverlapping convex polygons in the plane. Given two non-overlapping convex polygons P1 and P2 in the...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Erik D. Demaine, Martin L. Demaine, Perouz Taslakian, Godfried T. Toussaint
Sand drawings form a part of many cultural artistic traditions. Depending on the part of the world in which they occur, such drawings have different names such as sona, kolam, and Malekula drawings....
Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues (2008)
Demaine, Erik D., Demaine, Martin L., Fekete, Sandor P., Ishaque, Mashhood, Rafalin, Eynat, Schweller, Robert T., ...
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
A Locked Orthogonal Tree (2008)
Charlton, David, Demaine, Erik D., Demaine, Martin L., Price, Gregory, Tu, Yaa-Lirng
We give a counterexample to a conjecture of Poon [Poo06] that any orthogonal tree in two dimensions can always be flattened by a continuous motion that preserves edge lengths and avoids...
Hinged Dissections Exist (2007)
Abbott, Timothy G., Abel, Zachary, Charlton, David, Demaine, Erik D., Demaine, Martin L., Kominers, Scott D.
We prove that any finite collection of polygons of equal area has a common hinged dissection. That is, for any such collection of polygons there exists a chain of polygons hinged at vertices that can...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia
S. Skiena y The easiest way to refold a road map is differently.--- Jones's Rule of the Road (M. Gardner [3]) 1
Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, ...
. While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
More Games of No Chance MSRI Publications (2007)
Erik D. Demaine, Martin L. Demaine, David Eppstein
Abstract. We show that, in John Conway’s board game Phutball (or Philosopher’s Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Abstract. Clobber is a new two-player board game. In this paper, we introduce the 1-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by...
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
We prove that there is a polyhedron with genus 6 whose faces are orthogonal polygons (equivalently, rectangles) and yet the angles between some faces are not multiples of 90, so the polyhedron itself...
Cenek Timothy, M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, ...
While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
Erik D. Demaine, Martin L. Demaine, Anna Lubiw
The logo for CCCG this year is in fact an origami crease pattern, with the property that if you fold it at, all the bold lines outlining the letters line up, so
Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang
b;1
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a at folding by a sequence of simple folds?...
On rolling cube puzzles (2007)
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-khechen, Sándor P. Fekete, ...
We analyze the computational complexity of various rolling cube puzzles. 1
The Helium Stockpile : A Collaboration in Mathematical Folding Sculpture (2006)
Demaine, Erik D., Demaine, Martin L., Palmer, A. Laurie.
Leonardo - Volume 39, Number 3, June 2006
Locked and Unlocked Chains of Planar Shapes (2006)
Connelly, Robert, Demaine, Erik D., Demaine, Martin L., Fekete, Sandor P., Langerman, Stefan, Mitchell, Joseph S. B., ...
We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid...
Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman
We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most...
Locked and unlocked chains of planar shapes (2006)
Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, ...
We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid...
Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman
We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most...
Locked and unlocked chains of planar shapes (2006)
Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor Fekete, Stefan Langerman, ...
If we attach to each bar in a polygonal chain a rigid shape whose inward normals all hit the attached bar, and the resulting hinged chain of shapes does not overlap itself, then this chain can always...
Hinged dissection of polypolyhedra (2005)
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine
Fig. 1. Hinged dissection ofsquare and equilateral triangle [8]. Different shades showdifferent folded states.
Hinged dissection of polyominoes and polyforms (2005)
Erik D. Demaine, Martin L. Demaine, Greg N. Frederickson, Erich Friedman
Hinged dissection of polyominoes and polyforms (2005)
Erik D. Demaine, Martin L. Demaine, Erich Friedman Z
This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is de ned generally...
Hinged Dissection of Polyominoes and Polyforms (2005)
Erik Demaine Martin, Martin L. Demaine, Erich Friedman
This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is defined...
Hinged Dissection of Polyominoes and Polyforms (2005)
Erik Demaine Martin, Martin L. Demaine, Erich Friedman
This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is defined...
Hinged dissection of polypolyhedra (2005)
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine
Abstract. This paper presents a general family of 3D hinged dissections for polypolyhedra, i.e., connected 3D solids formed by joining several rigid copies of the same polyhedron along identical...
Hinged dissection of polyominoes and polyforms (2005)
Erik D. Demaine, Martin L. Demaine, Erich Friedman Z
This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is de ned generally...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Abstract. Clobber is a new two-player board game. In this paper, we introduce the 1-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the oneplayer variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf H.
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white...
Demaine, Erik D., Demaine, Martin L., Verrill, Helena A.
We introduce a new family of one-player games, involving the movement of coins from one configuration to another. Moves are restricted so that a coin can be placed only in a position that is adjacent...
The complexity of Clickomania (2002)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
Abstract. We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player...
The complexity of Clickomania (2002)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles (2002)
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
The Complexity of Clickomania (2001)
Biedl, Therese C., Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf, Jacobsen, Lars, Munro, J. Ian
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Enumerating Foldings and Unfoldings between Polygons and Polytopes (2001)
Demaine, Erik D., Demaine, Martin L., Lubiw, Anna, O'Rourke, Joseph
We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous questions for unfolding...
When can you fold a map (2001)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
Abstract. We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple...
Recent results in computational origami (2001)
Erik D. Demaine, Martin L. Demaine
Computational origami is a recent branch of computer science studying ecient algorithms for solving paper-folding problems. This eld essentially began with Robert Lang's work on algorithmic...
When Can You Fold a Map? (2000)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Demaine, Martin L., Mitchell, Joseph S. B., Sethia, Saurabh, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Phutball Endgames are Hard (2000)
Demaine, Erik D., Demaine, Martin L., Eppstein, David
We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the...
Demaine, Erik D., Demaine, Martin L., Lubiw, Anna, O'Rourke, Joseph
We investigate how to make the surface of a convex polyhedron (a polytope) by folding up a polygon and gluing its perimeter shut, and the reverse process of cutting open a polytope and unfolding it...
PushPush and Push-1 are NP-hard in 2D (2000)
Demaine, Erik D., Demaine, Martin L., O'Rourke, Joseph
We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game...
PushPush is NP-hard in 2D (2000)
Demaine, Erik D., Demaine, Martin L., O'Rourke, Joseph
We prove that a particular pushing-blocks puzzle is intractable in 2D, improving an earlier result that established intractability in 3D [OS99]. The puzzle, inspired by the game *PushPush*, consists...
PushPush and Push-1 are NP-hard in 2D (2000)
Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game...
Polygons Cuttable by a Circular Saw (2000)
Erik D. Demaine, Martin L. Demaine, Craig S. Kaplan
We introduce and characterize a new class of polygons that models wood, stone, glass, and ceramic shapes that can be cut with a table saw, lapidary trim saw, or other circular saw. In this model, a...
PushPush and Push-1 are NP-hard in 2D (2000)
Erik Demaine Martin, Martin L. Demaine
We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game...
PushPush is NP-hard in 2D (2000)
Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
We prove that a particular pushing-blocks puzzle is intractable in 2D, improving an earlier result that established intractability in 3D [OS99]. The puzzle, inspired by the game PushPush, consists of...
PushPush and Push-1 are NP-hard in 2D (2000)
Erik L. Demaine, Joseph O'Rourke, Martin L. Demaine
We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game...
Erik D. Demaine, Martin L. Demaine, Helena A. Verrill
Abstract. We introduce a new family of one-player games, involving the movement of coins from one configuration to another. Moves are restricted so that a coin can be placed only in a position that...
Hinged Dissection of Polyominoes and Polyforms (1999)
Demaine, Erik D., Demaine, Martin L., Eppstein, David, Frederickson, Greg N., Friedman, Erich
A hinged dissection of a set of polygons S is a collection of polygonal pieces hinged together at vertices that can be folded into any member of S. We present a hinged dissection of all edge-to-edge...
Erik D. Demaine, Martin L. Demaine
We show a remarkable fact about folding paper: From a single rectangular sheet of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if...
Erik D. Demaine, Martin L. Demaine
We show a remarkable fact about folding paper: From a single square of paper, one can fold it into a at origami that takes the (scaled) shape of any connected polygonal region, even if it has holes....
Erik D. Demaine, Martin L. Demaine
We show a remarkable fact about folding paper: From a single square of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if it has...
Erik D. Demaine, Martin L. Demaine
We show a remarkable fact about folding paper: From a single rectangular sheet of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if...
Polyhedral sculptures with hyperbolic paraboloids (1999)
Erik D. Demaine, Martin L. Demaine, Anna Lubiw
This paper describes the results of our experiments with gluing together partial hyperbolic paraboloids, or hypars. We make a paper model of each hypar by folding a polygonal piece of paper along...
Hiding Disks in Folded Polygons (1998)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Godfried T. Toussaint
This paper considers the problem of finding a simple fold of a given polygon P that "hides" (covers both sides of) the largest possible disk. We solve this problem by giving a...
Folding and Cutting Paper (1998)
Erik D. Demaine, Martin L. Demaine, Anna Lubiw
. We present an algorithm to find a flat folding of a piece of paper, so that one complete straight cut on the folding creates any desired plane graph of cuts. The folds are based on the straight...
Planar Drawings of Origami Polyhedra (1998)
Erik Demaine, Martin L. Demaine
this paper [1], we describe a linear-time algorithm for computing such a drawing directly from the topology of the medial axis, producing what we call the natural drawing ; see Fig. 3. ! ! ! Fig. 3....
Folding Any Silhouette from a Strip
Erik D. Demaine, Martin L. Demaine
this paper [4], we describe two other methods for solving this problem. The first method generalizes the notion of rings to make the minimum required strip width bounded by the minimum feature size...