New geometric algorithms for fully connected staged self-assembly
© 2016 Elsevier B.V. We consider staged self-assembly systems, in which square-shaped tiles can be added to bins in several stages. Within these bins, the tiles may connect to each other, depending on the glue types of their edges. Previous work by Demaine et al. showed that a relatively small numbe...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135768 |
| _version_ | 1811086722740518912 |
|---|---|
| author | Demaine, Erik D Fekete, Sándor P Scheffer, Christian Schmidt, Arne |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D Fekete, Sándor P Scheffer, Christian Schmidt, Arne |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | © 2016 Elsevier B.V. We consider staged self-assembly systems, in which square-shaped tiles can be added to bins in several stages. Within these bins, the tiles may connect to each other, depending on the glue types of their edges. Previous work by Demaine et al. showed that a relatively small number of tile types suffices to produce arbitrary shapes in this model. However, these constructions were only based on a spanning tree of the geometric shape, so they did not produce full connectivity of the underlying grid graph in the case of shapes with holes; self-assembly of fully connected assemblies with a polylogarithmic number of stages was left as a major open problem. We resolve this challenge by presenting new systems for staged assembly that produce fully connected polyominoes in O(log2n) stages, for various scale factors and temperature τ=2 as well as τ=1. Our constructions work even for shapes with holes and use only a constant number of glues and tiles. Moreover, the underlying approach is more geometric in nature, implying that it promises to be more feasible for shapes with compact geometric description. |
| first_indexed | 2024-09-23T13:32:47Z |
| format | Article |
| id | mit-1721.1/135768 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:32:47Z |
| publishDate | 2021 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1357682023-03-15T20:40:09Z New geometric algorithms for fully connected staged self-assembly Demaine, Erik D Fekete, Sándor P Scheffer, Christian Schmidt, Arne Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2016 Elsevier B.V. We consider staged self-assembly systems, in which square-shaped tiles can be added to bins in several stages. Within these bins, the tiles may connect to each other, depending on the glue types of their edges. Previous work by Demaine et al. showed that a relatively small number of tile types suffices to produce arbitrary shapes in this model. However, these constructions were only based on a spanning tree of the geometric shape, so they did not produce full connectivity of the underlying grid graph in the case of shapes with holes; self-assembly of fully connected assemblies with a polylogarithmic number of stages was left as a major open problem. We resolve this challenge by presenting new systems for staged assembly that produce fully connected polyominoes in O(log2n) stages, for various scale factors and temperature τ=2 as well as τ=1. Our constructions work even for shapes with holes and use only a constant number of glues and tiles. Moreover, the underlying approach is more geometric in nature, implying that it promises to be more feasible for shapes with compact geometric description. 2021-10-27T20:29:12Z 2021-10-27T20:29:12Z 2017 2019-06-12T13:24:12Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135768 en 10.1016/J.TCS.2016.11.020 Theoretical Computer Science Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Demaine, Erik D Fekete, Sándor P Scheffer, Christian Schmidt, Arne New geometric algorithms for fully connected staged self-assembly |
| title | New geometric algorithms for fully connected staged self-assembly |
| title_full | New geometric algorithms for fully connected staged self-assembly |
| title_fullStr | New geometric algorithms for fully connected staged self-assembly |
| title_full_unstemmed | New geometric algorithms for fully connected staged self-assembly |
| title_short | New geometric algorithms for fully connected staged self-assembly |
| title_sort | new geometric algorithms for fully connected staged self assembly |
| url | https://hdl.handle.net/1721.1/135768 |
| work_keys_str_mv | AT demaineerikd newgeometricalgorithmsforfullyconnectedstagedselfassembly AT feketesandorp newgeometricalgorithmsforfullyconnectedstagedselfassembly AT schefferchristian newgeometricalgorithmsforfullyconnectedstagedselfassembly AT schmidtarne newgeometricalgorithmsforfullyconnectedstagedselfassembly |