-
Article
Open AccessUnlocking history through automated virtual unfolding of sealed documents imaged by X-ray microtomography
Computational flattening algorithms have been successfully applied to X-ray microtomography scans of damaged historical documents, but have so far been limited to scrolls, books, and documents with one or two ...
-
Chapter and Conference Paper
Negative Instance for the Edge Patrolling Beacon Problem
Can an infinite-strength magnetic beacon always “catch” an iron ball, when the beacon is a point required to be remain nonstrictly outside a polygon, and the ball is a point always moving instantaneously and m...
-
Chapter and Conference Paper
Packing Cube Nets into Rectangles with O(1) Holes
We show that the 11 hexomino nets of the unit cube (using arbitrarily many copies of each) can pack disjointly into an \(m \times n\) ...
-
Chapter and Conference Paper
Toward Unfolding Doubly Covered n-Stars
We present nonoverlap** general unfoldings of two infinite families of nonconvex polyhedra, or more specifically, zero-volume polyhedra formed by double-covering an n-pointed star polygon whose triangular point...
-
Article
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
We prove that path puzzles with complete row and column information—or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint—are strongly NP-complete, ASP-complete, and #P-complete. Alo...
-
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. ...
-
Article
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
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
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
In the classical model of tile self-assembly, unit square tiles translate in the plane and attach edgewise to form large crystalline structures. This model of self-assembly has been shown to be capable of asympto...
-
Chapter and Conference Paper
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
When can a plane graph with prescribed edge lengths and prescribed angles (from among {0,180°, 360°}) be folded flat to lie in an infinitesimally thick line, without crossings? This problem generalizes the cla...
-
Chapter
Variations on Instant Insanity
In one of the first papers about the complexity of puzzles, Robertson and Munro [14] proved that a generalized form of the then-popular Instant Insanity puzzle is NP-complete. Here we study several variations ...
-
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...
-
Article
Hinged Dissections Exist
We prove that any finite collection of polygons of equal area has a common hinged dissection. That is, for any such collection of polygons there exists a chain of polygons hinged at vertices that can be folded...
-
Chapter
Meshes Preserving Minimum Feature Size
The minimum feature size of a planar straight-line graph is the minimum distance between a vertex and a nonincident edge. When such a graph is partitioned into a mesh, the degradation is the ratio of original to ...
-
Article
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...
-
Article
Continuous Blooming of Convex Polyhedra
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a ...
-
Article
(Non)Existence of Pleated Folds: How Paper Folds Between Creases
We prove that the pleated hyperbolic paraboloid, a familiar origami model known since 1927, in fact cannot be folded with the standard crease pattern in the standard mathematical model of zero-thickness paper....
