![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron
We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid—for example, the surface of any polycube. The folding is e...
-
Chapter and Conference Paper
Dissection with the Fewest Pieces is Hard, Even to Approximate
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of
-
Chapter and Conference Paper
Continuous Flattening of Orthogonal Polyhedra
Can we flatten the surface of any 3-dimensional polyhedron P without cutting or stretching? Such continuous flat folding motions are known when P is convex, but the question remains open for nonconvex polyhedra. ...
-
Chapter and Conference Paper
Polynomial-Time Algorithm for Sliding Tokens on Trees
Suppose that we are given two independent sets I \(_{b}\) and I ...
-
Chapter and Conference Paper
Fun with Fonts: Algorithmic Typography
Over the past decade, we have designed five typefaces based on mathematical theorems and open problems, specifically computational geometry. These typefaces expose the general public in a unique way to intrigu...
-
Chapter and Conference Paper
Picture-Hanging Puzzles
We show how to hang a picture by wrap** rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when...
-
Chapter and Conference Paper
Folding Equilateral Plane Graphs
We consider two types of folding applied to equilateral plane graph linkages. First, under continuous folding motions, we show how to reconfigure any linear equilateral tree (lying on a line) into a canonical con...
-
Chapter and Conference Paper
Common Unfoldings of Polyominoes and Polycubes
This paper studies common unfoldings of various classes of polycubes, as well as a new type of unfolding of polyominoes. Previously, Knuth and Miller found a common unfolding of all tree-like tetracubes. By co...
-
Chapter and Conference Paper
Algorithms for Solving Rubik’s Cubes
The Rubik’s Cube is perhaps the world’s most famous and iconic puzzle, well-known to have a rich underlying mathematical structure (group theory). In this paper, we show that the Rubik’s Cube also has a rich u...
-
Chapter and Conference Paper
Making Polygons by Simple Folds and One Straight Cut
We give an efficient algorithmic characterization of simple polygons whose edges can be aligned onto a common line, with nothing else on that line, by a sequence of all-layers simple folds. In particular, such...
-
Chapter and Conference Paper
Algorithmic Folding Complexity
How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley str...
-
Chapter and Conference Paper
Minimal Locked Trees
Locked tree linkages have been known to exist in the plane since 1998, but it is still open whether they have a polynomial-time characterization. This paper examines the properties needed for planar trees to l...
-
Chapter and Conference Paper
Folding a Better Checkerboard
Folding an n ×n checkerboard pattern from a square of paper that is white on one side and black on the other has been thought for several years to require a paper square of semiperimeter n 2. Indeed...
-
Chapter and Conference Paper
Deflating the Pentagon
In this paper we consider deflations (inverse pocket flips) of n-gons for small n. We show that every pentagon can be deflated after finitely many deflations, and that any infinite deflation sequence of a pentago...
-
Chapter and Conference Paper
Hinged Dissection of Polypolyhedra
This paper presents a general family of 3D hinged dissections for polypolyhedra, i.e., connected 3D solids formed by joining several rigid copies of the same polyhedron along identical faces. (Such joinings are p...
-
Chapter and Conference Paper
When Can You Fold a Map?
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 of simple folds? There are se...