26 citations · 54 across the 9 of their papers we have counts for
6 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…
Flipturning polygons
Oswin Aichholzer, Carmen Cortes, Erik D. Demaine +7
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hu…
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…