Paper by Erik D. Demaine
- 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, to appear.
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(log2 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.
- This paper is available as arXiv:1505.07862.
- The paper is available in PDF (311k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ConnectedStagedAssembly_EuroCG2015 (New Geometric Algorithms for Staged Self-Assembly)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 21, 2017 by