25 Result(s)
within
Martin L. Demaine
Computer Science
Algorithm Analysis and Problem Complexity
-
Chapter and Conference Paper
Planar Drawings of Origami Polyhedra
This work studies the structure of origami bases via graph drawings of origami polyhedra. In particular, we propose a new class of polyhedra, called extreme-base polyhedra, that capture the essence of “extreme...
-
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...
-
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
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
Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and pe...
-
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
UNO Is Hard, Even for a Single Player
UNO \(\mbox{}^{\scriptsize\textregistered}\) is one of the world-wide well-known and popular card games. We investigate UNO from t...
-
Chapter and Conference Paper
Kaboozle Is NP-complete, Even in a Strip
Kaboozle is a puzzle consisting of several square cards, each annotated with colored paths and dots drawn on both sides and holes drilled. The goal is to join two colored dots with paths of the same color (and...
-
Chapter and Conference Paper
Matching Points with Things
Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point-object pairs. We show that when the objects we match the ...
-
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
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
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 ...
-
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
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...
