Tilt Automata: Gathering Particles With Uniform External Control
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912939680727040 |
|---|---|
| author | Fekete, Sándor P. Friemel, Jonas Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian |
| author_facet | Fekete, Sándor P. Friemel, Jonas Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian |
| contents | Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the tiles of a polyomino with all particles reacting uniformly to an external force by moving as far as possible in one of the four axis-parallel directions until they hit the boundary. The goal is to choose a sequence of directions that moves all particles to a common position. Our results include a polynomial-time algorithm for gathering in a completely filled polyomino as well as hardness reductions for approximating shortest gathering sequences and for determining whether the particles in a partially filled polyomino can be gathered. We pay special attention to the impact of restricted geometry, particularly polyominoes without holes. As corollaries, we make progress on an open question from [Balanza-Martinez et al., SODA 2020] by showing that deciding whether a given position can be occupied remains NP-hard in polyominoes without holes and provide initial results on the parameterized complexity of tilt problems. Our results build on a connection we establish between tilt models and the theory of synchronizing automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_02796 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tilt Automata: Gathering Particles With Uniform External Control Fekete, Sándor P. Friemel, Jonas Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian Computational Geometry Formal Languages and Automata Theory F.2.2 Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the tiles of a polyomino with all particles reacting uniformly to an external force by moving as far as possible in one of the four axis-parallel directions until they hit the boundary. The goal is to choose a sequence of directions that moves all particles to a common position. Our results include a polynomial-time algorithm for gathering in a completely filled polyomino as well as hardness reductions for approximating shortest gathering sequences and for determining whether the particles in a partially filled polyomino can be gathered. We pay special attention to the impact of restricted geometry, particularly polyominoes without holes. As corollaries, we make progress on an open question from [Balanza-Martinez et al., SODA 2020] by showing that deciding whether a given position can be occupied remains NP-hard in polyominoes without holes and provide initial results on the parameterized complexity of tilt problems. Our results build on a connection we establish between tilt models and the theory of synchronizing automata. |
| title | Tilt Automata: Gathering Particles With Uniform External Control |
| topic | Computational Geometry Formal Languages and Automata Theory F.2.2 |
| url | https://arxiv.org/abs/2603.02796 |