Geometric Amoebot Model

Besides the general Amoebot model, we will also consider the geometric amoebot model. The geometric amoebot model is a specific variant of the general amoebot model in which the underlying graph G is defined to be the Equilateral Triangular Graph Geqt 2. See Figure 2.1.

[…], Particles are anonymous but the bonds of each particle have unique labels. Therefore, a particle can uniquely identify each of its outgoing edges. We also assume that the particles have a common Chirality, i.e., they all have the same notion of clockwise direction, which allows each particle p to order its head bond labels. W.l.o.g.3, we assume that each particle labels its head and tail bonds from 0 to 5 in clockwise order. However, particles do not have a common sense of orientation since they can have different offsets of the labelings (Figure 2.2(b)). In Figure 2.2(a), we illustrate a set of particles (some contracted, some expanded) on the underlying graph Geqt.

Figure 2.2: (a) shows an example of a particle structure in the geometric amoebot model consisting of five particles on Geqt: the underlying graph Geqt is shown as a gray mesh; a particle occupying a single node, a contracted particle, is depicted as a black circle, and a particle occupying two nodes, an expanded particle, is depicted as two black circles connected by an edge. (b) depicts two particles occupying two non-adjacent positions on Geqt; the particles have different offsets for their head bond labelings.

Figure 2.3 illustrates an example of particles p and q executing a handover in Geqt. As the result of executing the handover, the expanded particle p contracts and the contracted particle q expands.

Figure 2.3: Two particles performing a handover. The left part shows an expanded particle p and a contracted particle q before executing the handover. The right part depicts the configuration of the particles after performing a handover. This ends up p to contract and q to expand.