52 citations · 271 across the 48 of their papers we have counts for
5 papers · 1 filter
When Can You Fold a Map?
Esther M. Arkin, Michael A. Bender, Erik D. Demaine +4
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…
Phutball Endgames are Hard
Erik D. Demaine, Martin L. Demaine, David Eppstein
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.…
Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes
Erik D. Demaine, Martin L. Demaine, Anna Lubiw +1
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…
PushPush and Push-1 are NP-hard in 2D
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 inspir…
PushPush is NP-hard in 2D
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 *P…