Step-Assembly with a Constant Number of Tile Types
Step-Assembly with a Constant Number of Tile Types
复制标题
具有恒定数量的瓷砖类型的分步组装
DOI：
10.1007/978-3-642-10631-6_96
复制
发表时间：
2009
影响因子：
5
通讯作者：
Christine Stoll
中科院分区：
文献类型：
--
作者：
Ján Manuch;L. Stacho;Christine Stoll
德缅因等人。艾尔[1]引入了一种用于构造自组装形状的分段组装模型，作为多瓦片模型的扩展[2]。在他们的模型中，组装在几个垃圾桶和几个阶段进行，在每个垃圾桶和每个阶段应用不同的瓷砖和超级瓷砖集。利用所有这些特征，他们证明了固定数量的瓷砖类型足以自组装任何给定的形状。
在本文中，我们考虑了一种简化的分段装配模型，称为阶梯式装配模型，在该模型中，每一步只有一个料仓，像标准装配模型一样，通过将瓦片逐个附着到成长的结构来进行装配。我们证明，在这个简化的模型中，固定数量的瓦片类型(24)足以组装一大类形状。对于一般的形状，我们注意到该模型的瓦片复杂度与该形状的生成树的单调连通节点搜索数有关。
Demaine et. al. [1] have introduced a model for staged assembly for constructing self-assembled shapes as an extension to the multiple tile model [2]. In their model the assembly proceeds in several bins and several stages with different sets of tiles and supertiles applied on each bin and in each stage. Taking advantage of all these features they showed that a constant number of tile types is sufficient to self-assemble any given shape.
In this paper, we consider a simplified model of staged assembly, called the step assembly model, in which we only have one bin in each step and assembly happens by attaching tiles one by one to the growing structure as in the standard assembly model. We show that in this simplified model a constant number of tile types (24) is sufficient to assemble a large class of shapes. This class includes all shapes obtained from any shape by scaling by a factor of 2. For general shapes, we note that the tile complexity of this model has connections to the monotone connected node search number of a spanning tree of the shape.