Skip to Main content Skip to Navigation

Self-assemblying (classes of) shapes with a constant number of tiles.

Abstract : Squares are the most studied shapes in the tile assembly model. Adleman et al. proved that the program size complexity of an $n \times n$ square is $\Theta(\frac{\log n}{\log\log n})$. In other words, for each $n$ we need a different set of tiles. Also, the size of the set increases with $n$. Our approach is to fix {\it a priori} the set of tiles in such a way that it always self-assembles into an $N \times N$ square. If $n$ is an arbitrary positive integer, we show how to calculate the tile concentrations in order to ensure that $\E(N)=n$. To our knowlwdge, the tile concentrations, a parameter of the original model, has never been seriously considered before. We claim that it is therefore not necessary to construct the tiles (which are in fact tiny molecules) for each shape we are asked to assemble. These tiny molecules are, for us, fixed primitives. In order to obtain (in expectation) the required shape, we only need to ``play'' with the concentrations. This is, of course, a standard procedure in Chemistry and Biology. Let $d$ be a distance in ${\Z}^2$. In the present work we tackle the specific problem of constructing tile systems that assemble into shapes of the form $\{ x \in {\Z}^2 \> \vert \> d(x,0) \leq N\}$ and such that $\E(N)=n$. We solve the problem for the max distance $d_{\infty}$ and for the $d_1$ distance. In the first case the induced shapes are squares while in the second case the induced shapes are diamonds. Diamonds are much more difficult to produce than squares. We leave as an open problem the Euclidean distance $d_2$, which induces the class of ``discrete circles''.
Document type :
Complete list of metadata
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:00 AM
Last modification on : Tuesday, May 4, 2021 - 9:10:01 PM


Files produced by the author(s)


  • HAL Id : hal-02101777, version 1



Ivan Rapaport, Eric Rémila. Self-assemblying (classes of) shapes with a constant number of tiles.. [Research Report] LIP RR-2004-38, Laboratoire de l'informatique du parallélisme. 2004, 2+12p. ⟨hal-02101777⟩



Record views


Files downloads