Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter

The paper looks at how to break a complex structure into simpler parts when the structure is made of many tiny robots (amoebots) on a grid, a common model for programmable matter. It focuses on an extension where amoebots can connect through reconfigurable circuits, letting robots quickly share information within each circuit. Earlier work achieved fast triangulation and a decomposition into tunnel regions, but only for restricted types of amoebot structures. Here, the authors define a decomposition into O(|H|) simple, geodesically convex regions that works for arbitrary amoebot structures. They show this decomposition can be computed in O(log n) rounds, where |H| is the number of holes. They also report improvements to a global maxima algorithm (and related spanning tree algorithm) for special cases, achieving O(log n) rounds with high probability.