New Geometric Algorithms for Fully Connected Staged Self-Assembly
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 suffi...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110845 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826211194007977984 |
|---|---|
| author | Fekete, Sándor P. Scheffer, Christian Schmidt, Arne Demaine, Erik D |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Fekete, Sándor P. Scheffer, Christian Schmidt, Arne Demaine, Erik D |
| author_sort | Fekete, Sándor P. |
| collection | MIT |
| description | 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; designing 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(log[superscript 2]n) stages, for various scale factors and temperature τ=2 as well as τ=1. Our constructions work even for shapes with holes and uses only a constant number of glues and tiles. Moreover, the underlying approach is more geometric in nature, implying that it promised to be more feasible for shapes with compact geometric description. |
| first_indexed | 2024-09-23T15:02:03Z |
| format | Article |
| id | mit-1721.1/110845 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:02:03Z |
| publishDate | 2017 |
| publisher | Springer |
| record_format | dspace |
| spelling | mit-1721.1/1108452022-10-02T00:09:23Z New Geometric Algorithms for Fully Connected Staged Self-Assembly Fekete, Sándor P. Scheffer, Christian Schmidt, Arne Demaine, Erik D Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D 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; designing 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(log[superscript 2]n) stages, for various scale factors and temperature τ=2 as well as τ=1. Our constructions work even for shapes with holes and uses only a constant number of glues and tiles. Moreover, the underlying approach is more geometric in nature, implying that it promised to be more feasible for shapes with compact geometric description. 2017-07-25T19:42:40Z 2017-07-25T19:42:40Z 2015-07 Article http://purl.org/eprint/type/ConferencePaper 978-3-319-21998-1 978-3-319-21999-8 0302-9743 1611-3349 http://hdl.handle.net/1721.1/110845 Demaine, Erik D. et al. “New Geometric Algorithms for Fully Connected Staged Self-Assembly.” DNA Computing and Molecular Programming. Ed. Andrew Phillips and Peng Yin. Vol. 9211. Cham: Springer International Publishing, 2015. 104–116. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-319-21999-8_7 DNA Computing and Molecular Programming Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Springer arXiv |
| spellingShingle | Fekete, Sándor P. Scheffer, Christian Schmidt, Arne Demaine, Erik D 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 | http://hdl.handle.net/1721.1/110845 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT feketesandorp newgeometricalgorithmsforfullyconnectedstagedselfassembly AT schefferchristian newgeometricalgorithmsforfullyconnectedstagedselfassembly AT schmidtarne newgeometricalgorithmsforfullyconnectedstagedselfassembly AT demaineerikd newgeometricalgorithmsforfullyconnectedstagedselfassembly |