Pattern Self-Assembly

Abstract

In the abstract Tile Assembly Model, self-assembling systems consisting of tiles of different colors can form structures on which colored patterns are “painted.” We explore the complexity, in terms of the unique tile types required, of assembling various patterns, proving several upper and lower bounds.

Overview

This paper concerns itself with the optimal complexity of construction of nxn patterns.

We first show constructions for three different simple patterns. A single-pixel pattern is a pattern where a single tile is set to black. A multi-pixel pattern is a pattern with a set of locations set to black such that the locations are \((\log n)\) distance away from each other. A striped pattern is a pattern where black stripes repeat themselves every \(i\) times horizontally and \(j\) times vertically. This paper provides constructions for each of these that use \(O(\log n)\) tile types.

A single black tile

Multiple black tiles)

Repeating black tiles)

[[File:GridRepeat.png|thumb|center|Repeating black tiles)]

This paper also shows that for almost all positive integers n, the tile complexity of weakly self-assembling 2-colored patterns on a n × n squares in the aTAM is \(\Theta(\frac{n^2}{\log n})\). This is done by proving this is lower bound for almost all patterns and by providing a construction for building any n x n square.

The skeleton. The green tile represents the seed

The square once the ribs of the skeleton have filled in (blue growing left, yellow growing right)

A set of Python and Java programs that generate aTAM systems related to these constructions, as well as example systems, can be downloaded here:

SelfAssembledPatterns code (Note that the latest version can be found at the bottom of the list.)