33 Result(s)
-
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
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...
-
Article
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
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...
-
Article
Puzzles, Art, and Magic with Algorithms
Solving and designing puzzles, creating sculpture and architecture, and inventing magic tricks all lead to fun and interesting algorithmic problems. This paper describes some of our explorations into these areas.
-
Article
Morpion Solitaire
We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most general form...
-
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...
-
Chapter and Conference Paper
Balanced k-Colorings
While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k ≥ 2, a set of vertices to minimize imbalance among a family of subsets of vertices. The...
-
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...
