---
abstract: |
    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 designing *universal configurations* that are capable of constructing a large class of shapes and patterns. For these constructions, we present the notions of *weak* and *strong* universality which indicate the presence of "excess" polyominoes after the shape is constructed. In particular, for given integers $h,w$, we show that there exists a strongly universal configuration with $\mathcal{O}(hw)$ $1 \times 1$ slidable particles that can be reconfigured to build any $h \times w$ patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any $h \times 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 motion planning in this model. We consider the problems of deciding if a board location can be occupied by any particle (occupancy problem), deciding if a specific particle may be relocated to another position (relocation problem), and deciding if a given configuration of particles may be transformed into a second given configuration (reconfiguration problem). We show all of these problems to be PSPACE-complete with the allowance of a single $2\times 2$ polyomino in addition to $1\times 1$ tiles. We further show that relocation and occupancy remain PSPACE-complete even when the board geometry is a simple rectangle if domino polyominos are included.
author:
- 'Jose Balanza-Martinez'
- David Caballero
- 'Angel A. Cantu'
- Luis Angel Garcia
- Timothy Gomez
- Austin Luchsinger
- Rene Reyes
- Robert Schweller
- Tim Wylie
bibliography:
- 'tam.bib'
- 'tilt.bib'
title: 'Full Tilt: Universal Constructors for General Shapes with Uniform External Forces[^1]'
---

Department of Computer Science\
University of Texas - Rio Grande Valley\
Edinburg, TX 78539-2999, USA\
{jose.balanzamartinez01, david.caballero01, angel.cantu01, luis.a.garcia01, timothy.gomez01, austin.luchsinger01, rene.reyes01, robert.schweller, rcain@example.org

1

Acknowledgments {#acknowledgments .unnumbered}
===============

We would like to thank Andrew Winslow for pointing us to the literature on the C2T gadget, which greatly simplified our proof of the complexity of the reconfiguration and relocation problems. We would also like to thank Aaron Becker for providing feedback on the final presentation of this work. Finally, we would like to thank the anonymous reviewers of the preliminary conference version of this paper for their thorough, careful, and constructive feedback.

[^1]: A preliminary version of this paper appeared in the Proceedings of the 2019 ACM-SIAM Symposium on Discrete Algorithms. This research was supported in part by National Science Foundation Grant CCF-1817602.

{'source': 'arXiv_out/1907'}