**Reference**:- Erik D. Demaine, Sándor Fekete, Christian Scheffer, and Arne Schmidt, “New Geometric Algorithms for Fully Connected Staged Self-Assembly”, in
*Proceedings of the 21st International Conference on DNA Computing and Molecular Programming (DNA 2015)*, Cambridge, Massachusetts, August 17–21, 2015, pages 104–116. **Abstract**:-
We consider
*staged self-assembly systems*, in which square-shaped Wang 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^{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. **Comments**:- This paper is available as arXiv:1505.07862.
**Availability**:- The paper is available in PDF (311k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- ConnectedStagedAssembly_TCS (New Geometric Algorithms for Fully Connected Staged Self-Assembly)
- ConnectedStagedAssembly_EuroCG2015 (New Geometric Algorithms for Staged Self-Assembly)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.