Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter
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_ | 1866915942209945600 |
|---|---|
| author | Hillebrandt, Henning Padalkin, Andreas Scheideler, Christian Warner, Daniel Werthmann, Julian |
| author_facet | Hillebrandt, Henning Padalkin, Andreas Scheideler, Christian Warner, Daniel Werthmann, Julian |
| contents | The decomposition of complex structures into simpler substructures is a powerful technique with a wide range of applications. We study the computation of decompositions in the context of programmable matter. The amoebot model is a well-established model for programmable matter, which places $n$ tiny robots called amoebots on the triangular grid. We consider the reconfigurable circuit extension of the geometric amoebot model, which allows amoebots to interconnect via so-called circuits. Amoebots can then instantaneously transmit simple beeps to all amoebots connected by the same circuit. Using reconfigurable circuits, previous papers have described a linear-time triangulation algorithm, and a logarithmic-time decomposition algorithm into so-called tunnel regions. Both algorithms only work on a restricted class of amoebot structures. In this paper, we define a decomposition into $O(|\mathcal H|)$ simple, geodesically convex regions for arbitrary amoebot structures, and show how it can compute such a decomposition in $O(\log n)$ rounds, where $|\mathcal H|$ denotes the number of holes in the amoebot structure. As a byproduct, we also improve the global maxima algorithm of Padalkin et al. (Nat. Comput., 2024) for special cases and with that also their spanning tree algorithm to $O(\log n)$ rounds w.h.p. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16112 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter Hillebrandt, Henning Padalkin, Andreas Scheideler, Christian Warner, Daniel Werthmann, Julian Distributed, Parallel, and Cluster Computing The decomposition of complex structures into simpler substructures is a powerful technique with a wide range of applications. We study the computation of decompositions in the context of programmable matter. The amoebot model is a well-established model for programmable matter, which places $n$ tiny robots called amoebots on the triangular grid. We consider the reconfigurable circuit extension of the geometric amoebot model, which allows amoebots to interconnect via so-called circuits. Amoebots can then instantaneously transmit simple beeps to all amoebots connected by the same circuit. Using reconfigurable circuits, previous papers have described a linear-time triangulation algorithm, and a logarithmic-time decomposition algorithm into so-called tunnel regions. Both algorithms only work on a restricted class of amoebot structures. In this paper, we define a decomposition into $O(|\mathcal H|)$ simple, geodesically convex regions for arbitrary amoebot structures, and show how it can compute such a decomposition in $O(\log n)$ rounds, where $|\mathcal H|$ denotes the number of holes in the amoebot structure. As a byproduct, we also improve the global maxima algorithm of Padalkin et al. (Nat. Comput., 2024) for special cases and with that also their spanning tree algorithm to $O(\log n)$ rounds w.h.p. |
| title | Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2604.16112 |