Title: Optimal Staged Self-Assembly of General Shapes
\nAuthors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
\nAbstract:
\nWe 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.
\nPublished: Arxiv, European Symposium on Algorithms (ESA’16), Algorithmica<\/p>\n
URL: https:\/\/link.springer.com\/article\/10.1007\/s00453-017-0318-0<\/p>\n
Journal Citation: Algorithmica, 80(4), 1383-1409, 2018. <\/p>\n
Bibtex:
\n@article{CMSVWW:2018:Algorithmica,
\n author=”Chalk, Cameron and Martinez, Eric and Schweller, Robert and Vega, Luis and Winslow, Andrew and Wylie, Tim”,
\n title=”Optimal Staged Self-Assembly of General Shapes”,
\n journal=”Algorithmica”,
\n year=”2018″,
\n month=”Apr”,
\n day=”01″,
\n volume=”80″,
\n number=”4″,
\n pages=”1383–1409″,
\n issn=”1432-0541″,
\n doi=”10.1007\/s00453-017-0318-0″,
\n url=”https:\/\/doi.org\/10.1007\/s00453-017-0318-0″
\n}<\/p>\n
Conference Citation: Proceedings of the 24th European Symposium of Algorithms (ESA’16), 57, 26:1–26:17, 2016. <\/p>\n","protected":false},"excerpt":{"rendered":"
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 … <\/p>\n