On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916586730815488 |
|---|---|
| author | Artmann, Matthias Padalkin, Andreas Scheideler, Christian |
| author_facet | Artmann, Matthias Padalkin, Andreas Scheideler, Christian |
| contents | In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the particle structure. Shape formation problems, where the particles have to reorganize themselves into a desired shape using basic movement abilities, are particularly interesting. In the related shape containment problem, the particles are given the description of a shape $S$ and have to find maximally scaled representations of $S$ within the initial configuration, without movements. While the shape formation problem is being studied extensively, no attention has been given to the shape containment problem, which may have additional uses beside shape formation, such as detection of structural flaws.
In this paper, we consider the shape containment problem within the geometric amoebot model for programmable matter, using its reconfigurable circuit extension to enable the instantaneous transmission of primitive signals on connected subsets of particles. We first prove a lower runtime bound of $Ω(\sqrt{n})$ synchronous rounds for the general problem, where $n$ is the number of particles. Then, we construct the class of snowflake shapes and its subclass of star convex shapes, and present solutions for both. Let $k$ be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within $\mathcal{O}(\log^2 k)$ rounds. If it is a snowflake but not star convex, we solve it within $\mathcal{O}(\sqrt{n} \log n)$ rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16892 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits Artmann, Matthias Padalkin, Andreas Scheideler, Christian Distributed, Parallel, and Cluster Computing In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the particle structure. Shape formation problems, where the particles have to reorganize themselves into a desired shape using basic movement abilities, are particularly interesting. In the related shape containment problem, the particles are given the description of a shape $S$ and have to find maximally scaled representations of $S$ within the initial configuration, without movements. While the shape formation problem is being studied extensively, no attention has been given to the shape containment problem, which may have additional uses beside shape formation, such as detection of structural flaws. In this paper, we consider the shape containment problem within the geometric amoebot model for programmable matter, using its reconfigurable circuit extension to enable the instantaneous transmission of primitive signals on connected subsets of particles. We first prove a lower runtime bound of $Ω(\sqrt{n})$ synchronous rounds for the general problem, where $n$ is the number of particles. Then, we construct the class of snowflake shapes and its subclass of star convex shapes, and present solutions for both. Let $k$ be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within $\mathcal{O}(\log^2 k)$ rounds. If it is a snowflake but not star convex, we solve it within $\mathcal{O}(\sqrt{n} \log n)$ rounds. |
| title | On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2501.16892 |