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 using the amoebot model. In particular, we show how to decompose arbitrary amoebot structures into O(|H|) hole-free, geodesically convex regions within O(log n) rounds (w.h.p.), where |H| denotes the number of holes in the amoebot structure.
Mittwoch, 17.06.2026
| 14.00 bis 14.30 Uhr
Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter
Ort: F2.419
Veranstalter: Henning Hillebrandt
Veranstalter: Henning Hillebrandt