Randomized Self Assembly of Rectangular Nano Structures

Abstract

Self assembly systems have numerous critical applications in medicine, circuit design, etc. For example, they can serve as nano drug delivery systems. The problem of assembling squares has been well studied. A lower bound on the tile complexity of any deterministic self assembly system for an N×N square is $\Omega(\frac{\log(N)}{\log(\log(N))})$ (inferred from the Kolmogrov complexity). Deterministic self assembly systems with an optimal tile complexity have been designed for squares and related shapes in the past. However designing $\Theta(\frac{\log(N)}{\log(\log(N))})$ unique tiles specific to a shape which needs to be self assembled is still an intensive task. Creating a copy of a tile is much simpler than creating a unique tile. With this constraint in mind probabilistic self assembly systems were introduced. These systems have O(1) tile complexity and the concentration of each of the tiles can be varied to produce the desired shape. Becker, et al. [1] introduced a line sampling technique which can self assemble m×n rectangles, where m is the expected width and n is the expected height of the rectangle. Kao, et al. [2] combined the line sampling technique with binary counters in a novel way to self assemble a supertile which can encode a binary string. This supertile can then be used to produce an n′×n′ square such that (1 − ε)n ≤ n′ ≤ (1 + ε)n (for some relevant ε) with probability ≥ 1 − δ for sufficiently large n (i.e., n ≥ f(ε,δ), for some appropriate function f). Doty[3] made the idea of Kao more precise, however the underlying construction is still based on sub-tiles to perform binary counting and division.

In this paper we present randomized algorithms that can self assemble squares, rectangles and rectangles with constant aspect ratio with high probability (i.e. Ω(1 − 1/n ^α), for any fixed α> 0) where n is the dimension of the shape which needs to be self assembled. Our self assembly constructions do not need any approximation frames introduced in Kao et al. [2] and hence are much cleaner and has significantly smaller constant in the tile complexity compared to both Kao [2] and Doty [3]. Finally In contrast to the existing randomized self assembly techniques our techniques can also self assemble a much stronger class of rectangles which have a fixed aspect ratio (α/β).