The leading model for exploring the complexity of self-assembly is Winfree’s tile assembly model, whose units are Wang tiles--squares with specific glues on each side, where glues of the same type bind to one another. A mix of tiles then self-assemble, if the binding affinity exceeds a threshold temperature. A typical task of considerable practical interest is to self-assemble into a specific shape, usually with one or two distinct temperature thresholds. It is important to minimize the number of distinct tiles (glue patterns) employed, because each batch of one type of tile needs to be built from DNA or by nanofabrication. A decade-old result shows that self-assembling an n × n square requires &THgr;(log n / log log n) tile types. It is disappointing that this function grows with n.

Inspired by the available practical manufacturing options, this paper alters the model to permit the assembly to proceed in stages, with intermediate batches stored in separate bins. A stage might involve adding several new types of tile into the solution or mixing the contents of two bins. Under this model, the authors are able to assemble an n × n square with a constant number of tile types (nine glues), employing a constant number of bins within O(log n) stages. They can reduce the number of stages to O(log log n) at the cost of increasing the number of bins to √log n.

The assembly follows a divide-and-conquer paradigm, partitioning the square into two pieces at each of the log n levels of a decomposition hierarchy. Then, the shape is assembled bottom-up in log n stages, using just a few bins to hold the emerging shape and the next two batches to be mixed. A challenge here is to ensure that two pieces have a unique joining, and so form the correct shape expected by the next level up the hierarchy. They accomplish this through a jigsaw technique--altering the shape of the boundaries of the pieces so that they may glue together in just one way.

Extensions of this basic idea lead to the assembly of arbitrary shapes with, again, only a constant number O(1) of tiles, at the cost of O(n) stages and bins.