Paper by Erik D. Demaine

Reference:

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.

Abstract:

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(log² n) stages. Our construction works even for shapes with holes and uses only a constant number of glues and tiles.

Availability:

The abstract is available in PDF (252k).

See information on file formats.

[Google Scholar search]

Related papers:

ConnectedStagedAssembly_TCS (New Geometric Algorithms for Fully Connected Staged Self-Assembly)

ConnectedStagedAssembly_DNA2015 (New Geometric Algorithms for Fully Connected Staged Self-Assembly)