Reducing Tile Complexity for the Self‐assembly of Scaled Shapes Through Temperature Programming

This paper concerns the self‐assembly of scaled‐up versions of arbitrary finite shapes. We work in the multiple temperature model that was introduced by Aggarwal, Cheng, Goldwasser, Kao, and Schweller (2005). The multiple temperature model is a natural generalization of Winfree’s abstract tile assembly model, where the temperature of a tile system is allowed to be shifted up and down as self‐assembly proceeds. We first exhibit two constant‐size tile sets in which scaled‐up versions of arbitrary shapes self‐assemble. Our first tile set has the property that each scaled shape self‐assembles via an asymptotically ‘Kolmogorov‐optimum’ temperature sequence but the scaling factor grows with the size of the shape being assembled. In contrast, our second tile set assembles each scaled shape via a temperature sequence whose length is proportional to the number of points in the shape but the scaling factor is a constant independent of the shape being assembled. We then show that there is no constant‐size tile set that can uniquely assemble an arbitrary (non‐scaled, connected) shape in the multiple temperature model, i.e., the scaling is necessary for self‐assembly. This answers an open question of Kao and Schweller ( 2006), who asked whether such a tile set exists.