Mathematics | Open Access Articles | Digital Commons Network™

Computational Geometry Column 36, Joseph O'Rourke Dec 1999

Computational Geometry Column 36, Joseph O'Rourke

Computer Science: Faculty Publications

Two results in "computational origami" are illustrated.

Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group Nov 1999

Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group

Computer Science: Faculty Publications

We prove that a particular pushing-blocks puzzle is intractable in 3D. 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 3D by reduction from SAT. The corresponding problem in 2D remains open.

Go to article

Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko Jun 1999

Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko

Computer Science: Faculty Publications

Everett et al. [EHN96, EHN97] introduced several varieties of stabbing information for the lines determined by pairs of vertices of a simple polygon P, and established their relationships to vertex visibility and other combinatorial data. In the same spirit, we define the “zero-parity (ZP) stabbing information” to be a natural weakening of their “weak stabbing information,” retaining only the distinction among {zero, odd, even > 0} in the number of polygon edges stabbed. Whereas the weak stabbing information’s relation to visibility remains an open problem, we completely settle the analogous questions for zero parity information, with three results: (1) ZP information …

Go to article

Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides Jan 1999

Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides

Computer Science: Faculty Publications

In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a …

Go to article

Computational Geometry Column 35, Joseph O'Rourke Jan 1999