26 citations · 58 across the 20 of their papers we have counts for
5 papers · 2 filters
Computational Geometry Column 40
Joseph O'Rourke
It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Thei…
Computational Geometry Column 39
Joseph O'Rourke
The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
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…