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

URL: https://link.springer.com/article/10.1007/s00453-017-0318-0

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.