## Self-Assembly of Any Shape with Constant Tile Types using High Temperature

Title: Self-Assembly of Any Shape with Constant Tile Types using High Temperature

Authors: Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie
Abstract:

Citation: Proc. of 26th European Symposium of Algorithms (ESA’18)
Bibtex:
PDF:

## Optimal Staged Self-Assembly of General Shapes

Title: Optimal Staged Self-Assembly of General Shapes
Authors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
Abstract:
We analyze the number of tile types t, bins b, and stages necessary to assemble $$n \times n$$ squares and scaled shapes in the staged tile assembly model. For $$n \times n$$ squares, we prove $$\mathcal {O}\left( \frac{\log {n} – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}\right)$$ stages suffice and $$\varOmega \left( \frac{\log {n} – tb – t\log t}{b^2}\right)$$ are necessary for almost all n. For shapes S with Kolmogorov complexity K(S), we prove $$\mathcal {O}\left( \frac{K(S) – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}\right)$$ stages suffice and $$\varOmega \left( \frac{K(S) – tb – t\log t}{b^2}\right)$$ are necessary to assemble a scaled version of S, for almost all S. We obtain similarly tight bounds when the more powerful flexible glues are permitted.
Published: Arxiv, European Symposium on Algorithms (ESA’16), Algorithmica

Journal Citation: Algorithmica, 80(4), 1383-1409, 2018.

Bibtex:
@article{CMSVWW:2018:Algorithmica,
author=”Chalk, Cameron and Martinez, Eric and Schweller, Robert and Vega, Luis and Winslow, Andrew and Wylie, Tim”,
title=”Optimal Staged Self-Assembly of General Shapes”,
journal=”Algorithmica”,
year=”2018″,
month=”Apr”,
day=”01″,
volume=”80″,
number=”4″,
pages=”1383–1409″,
issn=”1432-0541″,
doi=”10.1007/s00453-017-0318-0″,
url=”https://doi.org/10.1007/s00453-017-0318-0″
}

Conference Citation: Proceedings of the 24th European Symposium of Algorithms (ESA’16), 57, 26:1–26:17, 2016.