2026-07-20T12:08:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25850 2026-06-23T14:31:04Z ddc:004 open_access

Tilt Automata: Gathering Particles with Uniform External Control Fekete, Sándor P. Friemel, Jonas Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian Uniform control gathering full tilt polyominoes synchronizing automata 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 a corollary, 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. Our results build on a connection we establish between tilt models and the theory of synchronizing automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor P. Fekete and Jonas Friemel and Peter Kramer and Jan-Marc Reinhardt and Christian Rieck and Christian Scheffer 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.44 urn:nbn:de:0030-drops-258508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.44 eng https://creativecommons.org/licenses/by/4.0/legalcode