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 :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101777
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:00 AM
Last modification on : Wednesday, November 20, 2019 - 2:52:56 AM

File

RR2004-38.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101777, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

14

Files downloads

8