Coating in \(\textsf{SILBOT}\) with One Axis Agreement
摘要
In the context of Programmable Matter (PM), we consider the Coating problem. A swarm of weak and self-organizing computational entities, called particles, are required to move so as to ensure the closed surrounding of an object. As a model for PM, we consider the \(\textsf{SILBOT}\) , where asynchronous particles are modeled as finite state automata, living and operating on a triangular grid embedded in the plane. So far, within \(\textsf{SILBOT}\) , the Coating problem has been investigated for n particles sharing a common handedness, i.e., chirality. Here we investigate the case where particles share the direction of one axis of the coordinate system instead of chirality. We present a time optimal deterministic distributed algorithm – along with the correctness proof, that in \(\Theta (n^2)\) rounds solves the Coating problem, where a round concerns the minimal time window within which each particle is activated at least once.