Paper by Erik D. Demaine
- Erik D. Demaine, Sándor Fekete, and Arne Schmidt, “New Geometric Algorithms for Staged Self-Assembly”, in Abstracts from the 31st European Workshop on Computational Geometry (EuroCG 2015), Ljubljana, Slovenia, March 15–18, 2015, to appear.
We consider staged self-assembly, 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. In general,
self-assembly constructs complex (polyomino-shaped) structures from a limited
set of square tiles. Previous work by Demaine et al. considered a setting in
which assembly proceeds in stages. It was shown that a relatively small number
of tile types suffices to produce arbitrary shapes; 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. We
present new systems for stages assembly to assemble a fully connected
polyomino in O(log2 n) stages. Our construction
works even for shapes with holes and uses only a constant number of glues and
- The abstract is available in PDF (252k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ConnectedStagedAssembly_DNA2015 (New Geometric Algorithms for Fully Connected Staged Self-Assembly)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 25, 2017 by