Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
Computational Geometry Column 40, Joseph O'Rourke
Computational Geometry Column 40, Joseph O'Rourke
Computer Science: Faculty Publications
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. Their 3SAT-reduction proof is discussed.
On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Computer Science: Faculty Publications
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an N-link tree can have 2Ω(N) equivalence classes of configurations.
Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
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. The second construction answers a question we raised in [DDO00] for a variant we call Push-1. Both puzzles consist of unit square blocks on an integer lattice; all blocks are movable. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover when a …
Computational Geometry Column 39, Joseph O'Rourke
Computational Geometry Column 39, Joseph O'Rourke
Computer Science: Faculty Publications
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, Joseph O'Rourke
Examples, Counterexamples, And Enumeration Results For Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Computer Science: Faculty Publications
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 to a polygon. We explore basic enumeration questions in both directions: Given a polygon, how many foldings are there? Given a polytope, how many unfoldings are there to simple polygons? Throughout we give special attention to convex polygons, and to regular polygons. We show that every convex polygon folds to an infinite number of distinct polytopes, but that their number of combinatorially distinct gluings is …
Computational Geometry Column 38, Joseph O'Rourke
Computational Geometry Column 38, Joseph O'Rourke
Computer Science: Faculty Publications
Recent results on curve reconstruction are described.
Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke
Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
Open problems from the 15th Annual ACM Symposium on Computational Geometry.
Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
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 unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 2D by reduction from SAT.