Self-Assembly with Geometric Tiles

Details Self-Assembly with Geometric Tiles Self-Assembly with Geometric Tiles

2011-04-14

arxiv.org/abs/1104.2809v1

Computer Science

Computational Geometry

Scientific paper

In this work we propose a generalization of Winfree's abstract Tile Assembly Model (aTAM) in which tile types are assigned rigid shapes, or geometries, along each tile face. We examine the number of distinct tile types needed to assemble shapes within this model, the temperature required for efficient assembly, and the problem of designing compact geometric faces to meet given compatibility specifications. Our results show a dramatic decrease in the number of tile types needed to assemble $n \times n$ squares to $\Theta(\sqrt{\log n})$ at temperature 1 for the most simple model which meets a lower bound from Kolmogorov complexity, and $O(\log\log n)$ in a model in which tile aggregates must move together through obstacle free paths within the plane. This stands in contrast to the $\Theta(\log n / \log\log n)$ tile types at temperature 2 needed in the basic aTAM. We also provide a general method for simulating a large and computationally universal class of temperature 2 aTAM systems with geometric tiles at temperature 1. Finally, we consider the problem of computing a set of compact geometric faces for a tile system to implement a given set of compatibility specifications. We show a number of bounds on the complexity of geometry size needed for various classes of compatibility specifications, many of which we directly apply to our tile assembly results to achieve non-trivial reductions in geometry size.

Affiliated with

Also associated with

No associations

Rating

Self-Assembly with Geometric Tiles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Self-Assembly with Geometric Tiles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-Assembly with Geometric Tiles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-166997