Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
复制标题
Full Tilt：具有均匀外力的通用形状的通用构造函数
DOI：
10.1137/1.9781611975482.167
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wylie, Tim
中科院分区：
文献类型：
--
作者：
Balanza-Martinez, Jose;Luchsinger, Austin;Caballero, David;Reyes, Rene;Cantu, Angel;Schweller, Robert;Garcia, Luis;Wylie, Tim
我们研究的问题，组装一般的形状和模式的模型中，粒子移动的基础上统一的外力，直到他们遇到障碍。在该模型中，当彼此相邻时，对应的颗粒可以结合。简单地说，这个模型考虑了一个由“开放”和“封闭”空间组成的2D网格，沿着一组放置在棋盘上开放位置的可滑动多面体。板可以在4个基本方向中的任何一个方向倾斜，导致所有可滑动的多角形在指定方向上最大限度地移动，直到被阻挡。通过连续施加一系列这样的倾斜，沿着允许不同的多角形在相邻时粘附，倾斜序列提供了一种重新配置初始板配置的方法，以便将先前分离的多角形的集合组装成更大的形状。我们提出了设计通用配置的问题，这些通用配置能够构建一大类形状和图案。对于这些构造，我们提出了弱普适性和强普适性的概念，这表明在构造形状之后存在“多余”的多角形。特别地，对于给定的整数sh，w，我们证明了存在一个弱普适构型，其可滑动粒子数为O（hw）1 × 1，可重构为任意h × w模式矩形.然后我们扩展了这一结果，证明了存在一个弱普适构型，它可以构造任意h × w-有界尺寸的连通形.在这些结果之后，我们继续展示了一个强通用配置的存在，（没有多余的粒子），它可以组装任何形状在以前研究的“下降”类，而使用的空间平方小于以前的结果。最后，我们包括一个复杂的研究，决定是否一个粒子内的配置可以重新定位到另一个位置，以及决定是否可以将给定配置变换成第二给定配置。我们证明了这两个问题都是PSPACE完备的，即使没有粒子相互粘附，可移动粒子被限制在1 × 1瓦片和单个2 × 2 polyomino。
We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. In this model, corresponding particles may bond when adjacent with one another. Succinctly, this model considers a 2D grid of “open” and “blocked” spaces, along with a set of slidable polyominoes placed at open locations on the board. The board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. By successively applying a sequence of such tilts, along with allowing different polyominoes to stick when adjacent, tilt sequences provide a method to reconfigure an initial board configuration so as to assemble a collection of previous separate polyominoes into a larger shape.While previous work within this model of assembly has focused on designing a specific board configuration for the assembly of a specific given shape, we propose the problem of designinguniversal configurationsthat are capable of constructing a large class of shapes and patterns. For these constructions, we present the notions ofweakandstronguniversality which indicate the presence of “excess” polyominoes after the shape is constructed. In particular, for given integersh, w, we show that there exists a weakly universal configuration withO(hw) 1 × 1 slidable particles that can be reconfigured to build anyh×wpatterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build anyh×w-bounded size connected shape. Following these results, which require an admittedly relaxed assembly definition, we go on to show the existence of a strongly universal configuration (no excess particles) which can assemble any shape within a previously studied “drop” class, while using quadratically less space than previous results.Finally, we include a study of the complexity of deciding if a particle within a configuration may be relocated to another position, and deciding if a given configuration may be transformed into a second given configuration. We show both problems to be PSPACE-complete even when no particles stick to one another and movable particles are restricted to 1 × 1 tiles and a single 2 × 2 polyomino.
影响因子：
5.2
作者：
Schmidt, Arne;Manzoor, Sheryl;Fekete, Sandor P.
通讯作者：
Fekete, Sandor P.
影响因子：
2.1
作者：
Becker, Aaron T.;Demaine, Erik D.;Morris-Wright, Rose
通讯作者：
Morris-Wright, Rose