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:

Skip to content
# Tag: esa

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

## Optimal Staged Self-Assembly of General Shapes

Algorithmic Self-Assembly Research Group

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:

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.