The structural power of reconfigurable circuits in the amoebot model

<jats:title>Abstract</jats:title><jats:p>The <jats:italic>amoebot model</jats:italic> (Derakhshandeh et al. in: SPAA ACM, pp 220–222. <jats:ext-link xmlns:xlink="http://www.w3.org/1999/xlink" ext-link-type="doi" xlink:href="10.1145/2612669.2612712">https://doi.org/10.1145/2612669.2612712</jats:ext-link>, 2014) has been proposed as a model for programmable matter consisting of tiny, robotic elements called <jats:italic>amoebots</jats:italic>. We consider the <jats:italic>reconfigurable circuit extension</jats:italic> (Feldmann et al. in J Comput Biol 29(4):317–343. <jats:ext-link xmlns:xlink="http://www.w3.org/1999/xlink" ext-link-type="doi" xlink:href="10.1089/cmb.2021.0363">https://doi.org/10.1089/cmb.2021.0363</jats:ext-link>, 2022) of the geometric amoebot model that allows the amoebot structure to interconnect amoebots by so-called <jats:italic>circuits</jats:italic>. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with fundamental problems like the <jats:italic>stripe computation problem</jats:italic> where, given any connected amoebot structure <jats:italic>S</jats:italic>, an amoebot <jats:italic>u</jats:italic> in <jats:italic>S</jats:italic>, and some axis <jats:italic>X</jats:italic>, all amoebots belonging to axis <jats:italic>X</jats:italic> through <jats:italic>u</jats:italic> have to be identified. Second, we consider the <jats:italic>global maximum problem</jats:italic>, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can be used to solve the <jats:italic>skeleton problem</jats:italic>, where a cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions allows the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.</jats:p>