On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits

We use the geometric amoebot model for programmable matter, as proposed in [9]. Using the terminology from the recent canonical model description [8], we assume common direction and chirality, constant-size memory, and a fully synchronous scheduler, making it strongly fair. We describe the model in sufficient detail here and refer to [9, 8] for more information.

The geometric amoebot model places $n$ particles called amoebots on the infinite regular triangular grid graph $G_{\mathrm{\Delta }}=(V_{\mathrm{\Delta }},E_{\mathrm{\Delta }})$ (see Fig. 1(a)). This is the typical graph used in the amoebot literature [9, 12, 21, 20, 19]. Each amoebot occupies one node, and each node is occupied by at most one amoebot. We identify each amoebot with the grid node it occupies to simplify the notation. Thereby, we define the amoebot structure $A\subset V_{\mathrm{\Delta }}$ as the set of occupied nodes. We assume that $A$ is finite and its induced subgraph of $G_{\mathrm{\Delta }}$ is connected.

Each amoebot has a local compass identifying one of its incident grid edges as the East direction, and a chirality defining its local sense of clockwise rotation. We assume that all amoebots share both. This is not a restrictive assumption because a common compass and chirality can be established efficiently using circuits [12]. The amoebots are controlled in a distributed fashion by identical and anonymous finite state machines. In particular, the amount of memory per amoebot is constant, i.e., fixed by the algorithm/state machine running on each amoebot and independent of the number of amoebots in the structure. This means that, for example, unique identifiers for all amoebots cannot be stored. A computation proceeds in fully synchronous rounds. In each round, all amoebots act and change their states simultaneously based on their current state and their received signals (see Section 1.2). We measure the time complexity of an algorithm by the number of rounds it requires until all amoebots reach a terminal state. Although the model allows amoebots to perform movements, we only consider static amoebot structures in this paper.

The reconfigurable circuit extension [12] places $c_{\varphi }$ external links on every edge connecting two adjacent amoebots $u,v\in A$. The endpoints of an external link are called pins. For each link, one pin is owned by $u$ and one is owned by $v$. The constant $c_{\varphi }$ is an algorithm design parameter and is the same for all amoebots. In this paper, we use $c_{\varphi }=2$, which is the least number of pins required by the PASC algorithm [12], a central primitive for our results.

Let $P(u)$ be the set of pins owned by amoebot $u\in A$. Each amoebot $u$ computes a partitioning of $P(u)$ into a set $𝒬(u)$ of non-empty, pairwise disjoint subsets $Q\subseteq P(u)$ such that ${\bigcup }_{Q\in 𝒬(u)}Q=P(u)$. The subsets $Q\in 𝒬(u)$ are called partition sets and $𝒬(u)$ is called the pin configuration of $u$. The amoebot’s algorithm defines how the pin configuration is computed in every round. Let $𝒬:={\bigcup }_{u\in A}𝒬(u)$ be the set of all partition sets in the amoebot structure. Two partition sets $Q\in 𝒬(u)$ and $Q^{\prime }\in 𝒬(v)$ of neighboring amoebots $u$ and $v$ are connected if there is an external link with one pin in $Q$ and one pin in $Q^{\prime }$. Let $E_{𝒬}$ be the set of these connections. We call each connected component $C$ of the undirected graph $G_{𝒬}:=(𝒬,E_{𝒬})$ a circuit (see Figs. 1(c), 1(d)). An amoebot $u$ is part of a circuit $C$ if $C$ contains at least one partition set of $u$. Note that multiple partition sets of an amoebot $u$ may be contained in the same circuit without $u$ being aware of this due to its lack of global information.

During its activation, each amoebot can establish an arbitrary new pin configuration and send primitive signals called beeps on any selection of its partition sets. A beep is broadcast to the circuit containing the partition set it was sent on. All partition sets in that circuit receive the beep at the beginning of the next round. An amoebot can tell which of its partition sets have received a beep, but it has no information on the identity, location, or number of beeping amoebots. We model all communication between amoebots with circuits.

Consider the embedding of $G_{\mathrm{\Delta }}$ into ${ℝ}^2$ such that the grid’s faces form unit triangles and one grid node is placed at the plane’s origin $(0,0)\in {ℝ}^2$ (see Fig. 1(b)). We obtain three coordinate axes, $X,Y,Z$, and six cardinal directions $𝒟=\{\text{E},\text{NE},\text{NW},\text{W},\text{SW},\text{SE}\}$. Let ${𝒖}_d$ denote the unit vector in direction $d\in 𝒟$.

A shape $S\subset {ℝ}^2$ is a finite union of nodes, edges, and faces of the embedded grid graph (see Fig. 2, c.f. [10, 12]). Edges contain their endpoints and faces contain their enclosing edges. A shape must be connected, but it may contain holes, i.e., ${ℝ}^2\setminus S$ might not be connected. This shape definition matches the one used in [10] for shape formation and extends the definition used in [12] for shape recognition.

We define translation, rotation, and scaling operations on a shape $S$ as follows. For $t\in {ℝ}^2$, we denote $S$ translated by $t$ by $S+t:=\{p+t\mid p\in S\}$. This is a valid shape if and only if $t$ is the position of a grid node, i.e., a linear combination of unit vectors in the cardinal directions with integer coefficients. We can therefore write $t\in V_{\mathrm{\Delta }}$, identifying the position with the unique grid node occupying it. For $r\in \mathbb{Z}$, let $S^{(r)}$ denote $S$ after $r$ counter-clockwise rotations by ${60}^{\circ }$ around the origin of ${ℝ}^2$. Note that $r\in \{0,\mathrm{\dots },5\}$ is sufficient to represent all distinct rotations of a shape in the grid. Let $k\in ℝ$ be a scale factor, then we define $k\cdot S:=\{k\cdot p\mid p\in S\}$ to be the shape $S$ scaled by $k$. We only consider positive integer scale factors to ensure that the resulting set is a valid shape. If $S$ is minimal, i.e., there is no scale factor such that $k^{\prime }\cdot S$ is a valid shape, then the integer scale factors cover all possible scales of $S$ that produce valid shapes (see Lemma 1 in [10]). Two shapes are equivalent if one can be obtained from the other by a rigid motion, i.e., a composition of a translation and a rotation.

Let $V(S)\subset V_{\mathrm{\Delta }}$ denote the set of grid nodes contained in $S$. For convenience, we assume $(0,0)\in V(S)$ for any given shape $S$ and call this node the origin of $S$. This property is invariant under rotation and scaling as defined above. A valid placement of a shape $S$ in an amoebot structure $A$ is an amoebot $p\in A$ with $V(S+p)\subseteq A$ (identifying $p$ with the grid node it occupies). Let $𝒱(S,A)\subseteq A$ denote the set of all valid placements of $S$ in $A$. The maximum scale of $S$ in $A$ is the largest scale $k\in {\mathbb{N}}_0$ such that there is a valid placement of $k\cdot S^{(r)}$ in $A$ for some $r\in \mathbb{Z}$:

$k_{\max }$ is well-defined because $0\cdot S$ is at most a single node for every shape $S$, which fits into any non-empty amoebot structure $A$. We obtain $k_{\max }(S,A)=\mathrm{\infty }$ if and only if $S$ does not contain any edges. If $S$ and $A$ are clear from the context, we will write $k_{\max }=k_{\max }(S,A)$. See Fig. 3 for illustration.

We define the shape containment problem as follows: Let $S$ be a shape (containing the origin). An algorithm solves the shape containment problem instance $(S,A)$ for an amoebot structure $A$ if it terminates eventually and at the end,

1. 1.

   all amoebots know whether $k_{\max }\in \{0,\mathrm{\infty }\}$ (meaning that all or none of the amoebots are valid placements), and

2. 2.

   if $k_{\max }\in \mathbb{N}$, then for every $r\in \{0,\mathrm{\dots },5\}$, each amoebot knows whether it is contained in $𝒱(k_{\max }\cdot S^{(r)},A)$.

The algorithm solves the shape containment problem for $S$ if it solves the shape containment instances $(S,A)$ for all finite connected amoebot structures $A$. Note that the shape $S$ is fixed for an algorithm, i.e., it is encoded in the state machine in some way, and its size is constant. The algorithm may use an equivalent shape $S^{\prime }$ instead of $S$ itself.

There are two key challenges in solving the shape containment problem. First, the amoebots have to find the maximum scale $k_{\max }$. We approach this problem by testing individual scale factors for valid placements until $k_{\max }$ is fixed. We call this part of an algorithm the scale factor search. Second, for a given scale $k$ and a rotation $r$, the valid placements of $k\cdot S^{(r)}$ have to be identified. This means that every amoebot $p\in A$ must collect information on all amoebots in $V(k\cdot S^{(r)}+p)$. $p$ then has to mark itself as a valid placement if and only if all of these amoebots exist. In some cases, we initially view all amoebots as placement candidates and then eliminate candidates that can be ruled out as valid placements. We call this part the valid placement search procedure. Since the information about missing amoebots naturally comes from the boundaries of the structure, the main difficulty here is distributing this information efficiently to all affected amoebots and not ruling out any valid placements.

In this paper, we present sublinear time solutions for the shape containment problem using circuits. As a motivation, we first prove a lower bound for the general case that holds even if the maximum scale is known, by creating a communication bottleneck for an example shape. Next, we present scale factor search approaches using distributed memory, applying a binary search where it is possible. We then introduce simple and efficient primitives for placement search algorithms based on combining and transforming valid placements of lines, thereby constructing increasingly complex shapes. Using earlier results for reconfigurable circuits, these primitives run in at most logarithmic time. By combining our primitives, we obtain the class of snowflake shapes, which contains a variety of complex and practically relevant shapes. For example, it contains all convex shapes, all shapes that are composed of parallelograms of the same orientation, all shapes composed of hexagons, and combinations (e.g., unions) of these and other shapes. The definition of this class allows more types of shapes to be combined and integrated when a valid placement search procedure is given for them. Our shape containment solution for snowflakes takes a sublinear number of rounds. Further, we show that for the set of star convex shapes, which is contained in the snowflake class, a binary search for the scale factor even leads to a polylogarithmic solution. Surprisingly, the binary search approach is only directly applicable to star convex shapes. We only give high-level explanations of our primitives and defer the technical details and proofs to the full version of the paper [4]. Selected proofs can also be found in the appendix.

The authors of [12] demonstrated the potential of their reconfigurable circuit extension with algorithms solving the leader election, compass alignment, and chirality agreement problems within $𝒪(\log n)$ rounds, w.h.p.¹¹1An event holds with high probability (w.h.p.) if it holds with probability at least $1-n^{-\delta }$, where the constant $\delta$ can be made arbitrarily large. They also presented efficient solutions for some exact shape recognition problems: Given common chirality, an amoebot structure can determine whether it matches a scaled version of a given shape composed of edge-connected faces in $𝒪(1)$ rounds. Without common chirality, convex shapes can be detected in $𝒪(1)$ rounds and parallelograms with linear or polynomial side ratios can be detected in $\mathrm{\Theta }(\log n)$ rounds, w.h.p.

The PASC algorithm was introduced in [12] and refined in [21], and it allows amoebots to compute distances along chains. It has become a central primitive in the reconfigurable circuit extension, as it was used to construct spanning trees, detect symmetry, and identify centers and axes of symmetry in polylogarithmic time, w.h.p. [21]. The authors in [20] used it to solve the single- and multi-source shortest path problems, requiring $𝒪(\log \mathrm{\ell })$ rounds for a single source and $\mathrm{\ell }$ destinations and $𝒪(\log n{\log }^{2}k)$ rounds for $k$ sources and any number of destinations. The PASC algorithm also plays a crucial role in this paper (see Sec. 2.2.2).

The authors in [11] studied the capabilities of a generalized circuit communication model that directly extends the reconfigurable circuit model to general graphs. They provided polylogarithmic time algorithms for various common graph construction (minimum spanning tree, spanner) and verification problems (minimum spanning tree, cut, Hamiltonian cycle etc.). Additionally, they presented a generic framework for translating a type of lower bound proof from the widely used CONGEST model into the circuit model, demonstrating that some problems are hard in both models, while others can be solved much faster with circuits. For example, checking whether a graph contains a $5$-cycle takes $\mathrm{\Omega }(n/\log n)$ rounds in general graphs, even with circuits, while the verification of a connected spanning subgraph can be done with circuits in $𝒪(\log n)$ rounds w.h.p., which is below the lower bound shown in [22].

In the context of computational geometry, the basic polygon containment problem was studied in [6], focusing on the case where only translation and rotation are allowed. The problem of finding the largest copy of a convex polygon inside some other polygon was discussed in [23] and [1], for example. An example for the problem of placing multiple polygons inside another without any polygons intersecting each other is given by [17]. More recently, the authors in [16] showed lower bounds for several polygon placement cases under the $k$SUM conjecture. For example, assuming the $5$SUM conjecture, there is no $𝒪({(p+q)}^{3-\epsilon })$-time algorithm for any $\epsilon >0$ that finds a largest copy of a simple polygon $P$ with $p$ vertices that fits into a simple polygon $Q$ with $q$ vertices under translation and rotation. Perhaps more closely related to our setting (albeit centralized) is an algorithm that solves the problem of finding the largest area parallelogram inside of an object in the triangular grid, where the object is a set of edge-connected faces [2].

As mentioned before, we assume that all amoebots share a common compass direction and chirality. This is a reasonable assumption because the authors of [12] have presented randomized algorithms establishing both in $𝒪(\log n)$ rounds, w.h.p.

We often want to synchronize amoebots, for example, when different parts of the structure run independent instances of an algorithm simultaneously. For this, we can use a global circuit: Each amoebot connects all of its pins into a single partition set. The resulting circuit spans the whole structure and allows the amoebots which are not yet finished with their procedure to inform all other amoebots by sending a beep. When no beep is sent, all amoebots know that all instances of the procedure are finished. Due to the fully synchronous scheduler, we can establish the global circuit periodically at predetermined intervals.

A chain of amoebots with length $m-1$ is a sequence of $m$ amoebots $C=(p_0,\mathrm{\dots },p_{m-1})$ where all subsequent pairs $p_i,p_{i+1}$, , are neighbors, each amoebot except $p_0$ knows its predecessor, and each amoebot except $p_{m-1}$ knows its successor. In this paper, we only consider simple chains without multiple occurrences of the same amoebot. By letting each amoebot decide whether it connects a pin toward its predecessor with a pin toward its successor, we can easily establish circuits along such chains.

Next, we consider the Minkowski sum of a shape with a line.

The resulting subset of ${ℝ}^2$ is a valid shape, and if both shapes contain the origin, then their sum also contains the origin. Observe that for any shape $S$ and any line $\mathrm{L}(d,\mathrm{\ell })$, we have

i.e., $V(S\oplus \mathrm{L}(d,\mathrm{\ell }))$ consists of $\mathrm{\ell }+1$ consecutive copies of $V(S)$. This means that an amoebot $p$ is a valid placement of $S^{\prime }=S\oplus \mathrm{L}(d,\mathrm{\ell })$ if and only if it is a valid placement of the line $L=\mathrm{L}(d,\mathrm{\ell })$ and for every amoebot $q\in V(L+p)$, $q$ is a valid placement of $S$. Suppose the amoebots already know the set $C$ of valid placements of $S$ and store $\mathrm{\ell }$ in a binary counter. Then, they can find the valid placements of $S\oplus L$ by running the placement search for $L$ within $C$, treating the amoebots in $A\setminus C$ as if they did not exist, except for synchronization.

Observe that this already yields efficient valid placement search procedures for shapes like parallelograms $\mathrm{L}(d_1,{\mathrm{\ell }}_1)\oplus \mathrm{L}(d_2,{\mathrm{\ell }}_2)$ and unions thereof.

Consider some shape $S$, its valid placements $C=𝒱(S,A)$, a direction $d\in 𝒟$, and a distance $\mathrm{\ell }\in \mathbb{N}$ such that $\mathrm{\ell }\cdot {𝒖}_d\in S$. Now, let $S^{\prime }=S-\mathrm{\ell }\cdot {𝒖}_d$, then $S^{\prime }$ only differs from $S$ in the location of its origin, and the valid placements of $S^{\prime }$ are just translated versions of the placements of $S$, i.e., $𝒱(S^{\prime },A)=C+\mathrm{\ell }\cdot {𝒖}_d$. Given the valid placements of $S$, we can compute the placements of $S^{\prime }$ with a procedure that translates the placement information from $C$. Our translation primitive can do this efficiently for shapes with the following property:

For example, the minimal axis width of a triangular face is $0$ for all axes due to its corners, and the $W$-width of $\mathrm{L}(d,\mathrm{\ell })$ is $\mathrm{\ell }$ when $d$ is parallel to $W$ and $0$ otherwise. Further, observe that for any shape $S$, direction $d$ on axis $W$, and $\mathrm{\ell }\in \mathbb{N}$, the $W$-width of $S\oplus \mathrm{L}(d,\mathrm{\ell })$ is at least $\mathrm{\ell }$.

Now, consider a $W$-wide shape $S$ and let $C=𝒱(k\cdot S,A)$ for some scale $k\in \mathbb{N}$. Note that $k\cdot S$ has a $W$-width of at least $k$. Let $q\in A\setminus C$ be an invalid placement of $k\cdot S$, then $q$ must be part of a $W$-segment of $A\setminus C$ that has length at least $k$ or is bounded by unoccupied nodes on at least one side. This is because any unoccupied node $x\in V_{\mathrm{\Delta }}\setminus A$ that makes $q$ invalid lies in $V(k\cdot S+q)$. Since $V(k\cdot S)$ consists of $W$-segments of length at least $k$, $x$ causes a similar segment which contains $q$ to be invalid, as any placement in this segment is also invalidated by $x$.

For translating the valid placements $C$ of $k\cdot S$ by $k$ steps in a direction $d$ parallel to $W$, suppose that $\mathrm{L}(d,1)\subseteq S$ (otherwise, we add this edge as part of the shape transformation). Then, we can reduce the problem to translating a single segment of length at least $k$. For this, we run a procedure in every maximal $W$-segment $M$ of $A$ simultaneously. Suppose we want to translate some segment $C_M$ in $M$. It suffices to translate the start $p_1$ and endpoint $p_2$ of $C_M$, identifying $p_1^{\prime }=p_1+k\cdot {𝒖}_d$ and $p_2^{\prime }=p_2+k\cdot {𝒖}_d$. To identify $p_i^{\prime }$, the amoebots in $M$ run the PASC algorithm with $p_i$ as the start point while transmitting $k$ on a global circuit. Each amoebot compares its distance to $p_i$ to $k$, and the amoebot with distance equal to $k$ becomes $p_i^{\prime }$. Afterward, the amoebots in $M$ establish a chain circuit between $p_1^{\prime }$ and $p_2^{\prime }$, and send a beep that is received by all amoebots on the translated segment. Due to the size of the considered segments $C_M$, this procedure can run for almost all segments within $M$ simultaneously without interference. The translation primitive moves the origin of a $W$-wide shape on the axis $W$ and adds the line connecting the old and new origin locations.

Finally, we show how to find the valid placements of triangles using the above primitives. Line shapes are scaled edges and triangles are scaled faces.

To construct the valid placements of $T=\mathrm{T}(d,\mathrm{\ell })$, we cover $V(T)$ with the union of three parallelograms. The side lengths of the parallelograms are ${\mathrm{\ell }}^{\prime }=\lfloor \mathrm{\ell }/2\rfloor$ and ${\mathrm{\ell }}^{\prime \prime }=\lfloor \mathrm{\ell }/2\rfloor +(\mathrm{\ell }mod2)$. Two parallelograms are translated to reach the corners of the triangle. The algorithm can be summarized as follows: The amoebots first compute ${\mathrm{\ell }}^{\prime }$ and ${\mathrm{\ell }}^{\prime \prime }$ on the binary counter storing $\mathrm{\ell }$. Then, they run the line primitive to compute the valid placements of three lines of length ${\mathrm{\ell }}^{\prime }$ or ${\mathrm{\ell }}^{\prime \prime }$. Next, they apply the Minkowski sum primitive to the three sets of line placements, resulting in the valid placements of three parallelograms. To translate two of the parallelograms, they run the translation primitive, which is applicable since the parallelograms have a width of at least ${\mathrm{\ell }}^{\prime }$ on the translation axis (for a translation by ${\mathrm{\ell }}^{\prime \prime }={\mathrm{\ell }}^{\prime }+1$, the valid placements can be moved by one more step in a single round using only local communication). Finally, they intersect the valid placements of all three parallelograms (union operation) to obtain the valid placements of the triangle.

Combining the primitives discussed in the previous section, we obtain the following class of shapes. Our definition identifies shapes with trees such that every node in the tree represents a shape and every edge represents a composition or transformation of shapes.

Note that this definition constrains the location of a snowflake’s origin. Because algorithms for the shape containment problem can place the origin of a shape freely, we may include equivalent shapes in the class of snowflakes. Our algorithms always place the origin by the definition. Fig. 5 shows examples for snowflakes and non-snowflake shapes.

To compute the valid placements of a snowflake, we apply the primitives from Section 5 following a topological ordering of the shape’s tree representation. This way, the amoebots first compute valid placements of primitive shapes (lines and triangles), and then they apply the union, Minkowski sum, and translation operations successively until they arrive at the valid placements of the shape represented by the root node. This sequence of operations is encoded in the state machine of each amoebot; we say that the amoebots “have access” to the shape and its tree representation.

Consider a snowflake $S$ represented by a tree $T=(V_T,E_T)$ with labelings $\tau (\cdot )$, $d(\cdot )$ and $\mathrm{\ell }(\cdot )$. We assume that each amoebot has access to a representation of $T$ and a topological ordering of $T$ from the leaves to the root. The amoebots compute $𝒱(k\cdot S,A)$ as follows:

1. 1.

   For every leaf $v\in V_T$, perform the placement search for the scaled primitive $\mathrm{L}(d(v),k\cdot \mathrm{\ell }(v))$ or $\mathrm{T}(d(v),k\cdot \mathrm{\ell }(v))$ represented by $v$. Let $C(v)\subseteq A$ be the resulting set of valid placements.

2. 2.

   Process each non-leaf node $v\in V_T$ in the topological ordering as follows:

   1. (a)

      If $\tau (v)=\cup$, then set $C(v)={\bigcap }_{i=1}^{m}C(u_i)$, where the $u_i$ are the child nodes of $v$.

   2. (b)

      If $\tau (v)=\oplus$, let $u$ be the unique child of $v$. Run the procedure from Section 5.1 to compute $C(v)$ from $C(u)$.

   3. (c)

      If $\tau (v)=+$, let $u$ be the unique child of $v$. Run the procedure from Section 5.2 to compute $C(v)$ from $C(u)$.

3. 3.

   Let $r\in V_T$ be the root of $T$. Terminate with success ($k_{\max }\in \mathbb{N}$) and report the valid placements as $𝒱(k\cdot S,A)=C(r)$ if $C(r)\ne \mathrm{\varnothing }$, otherwise terminate with failure ($k_{\max }=0$).

The class of snowflake shapes is the result of our primitive operations and is therefore somewhat artificial. However, it contains a large variety of shapes, and its modular definition provides a framework for constructing efficient valid placement search algorithms for more shapes. For example, any shape that is composed of parallelograms with the same orientation is a snowflake, even if the parallelograms are only connected at the corners. This is because a parallelogram $\mathrm{L}(d_1,{\mathrm{\ell }}_1)\oplus \mathrm{L}(d_2,{\mathrm{\ell }}_2)$ is both $W_1$-wide and $W_2$-wide, where $W_i$ is the axis of $d_i$. Therefore, the translation primitive can be used to move the shape’s origin to any position in the parallelogram, after which the union primitive allows the addition of another parallelogram at this position. Since this maintains the width properties, it can be repeated until all parallelograms have been added to the shape. A similar method is possible for shapes composed of hexagons because hexagons are even wide on all three axes. Constructing shapes out of building blocks like parallelograms is a popular approach for shape formation in grid-based modular robot systems [19, 3]. Shapes in square grid models can be represented by parallelograms in the triangular grid. Furthermore, any valid placement search algorithm for non-snowflake shapes can be integrated into this framework as a primitive to expand the set of shapes.

To combine our valid placement search procedure with a scale factor search, we would like to know for which shapes the binary search approach is applicable. Recall from Section 4 that at least self-contained shapes permit a binary search. In this section, we characterize this class of shapes exactly as the star convex shapes.

For example, all convex shapes are star convex since all their nodes are centers. It is easy to see that star convex shapes are self-contained: When placing the origin of $S$ on a center node, no translation is necessary and $k\cdot S\subseteq k^{\prime }\cdot S$ holds for all . We can even show that only star convex shapes are self-contained. As the authors of [15] point out in their extensive survey on starshaped sets (see p. 1007), the results in [18] show that these two properties are equivalent in much more general settings when rotations are omitted.

The main proof and supporting lemmas can be found in Appendix B. In our context, this equivalence implies that the efficient binary search can only be applied directly to star convex shapes. For any non-star convex shape $S$, there exist an amoebot structure $A$ and scale factors $k,k^{\prime }$, , such that $𝒱(k\cdot S^{(r)},A)=\mathrm{\varnothing }$ for all $r$ but $𝒱(k^{\prime }\cdot S^{(r)},A)\ne \mathrm{\varnothing }$ for some $r$; consider, e.g., $A=V(k^{\prime }\cdot S)$ for sufficiently large $k$ and $k^{\prime }$. The proof of Theorem 21 shows that this always holds for infinitely many scales $k,k^{\prime }$.

Finally, we obtain algorithms solving the shape containment problem by combining valid placement search procedures with suitable scale factor search methods. First, we observe that star convex shapes are snowflakes:

This implies that we can solve the shape containment problem for a star convex shape $S$ in just $𝒪({\log }^2{k}_{\max }(S,A))$ rounds by using a binary search. For a snowflake $S$ that is not star convex, we apply the linear search approach, which runs $𝒪(K)$ valid placement searches when given some upper bound $K\ge k_{\max }(S,A)$. To obtain this upper bound, we use the observation that a snowflake without faces will always be a union of line shapes meeting at the origin, and therefore star convex. Thus, a non-star convex snowflake must contain at least one face, so $K=k_{\max }(\mathrm{T}(d,1),A)$ is a suitable upper bound (for any $d\in 𝒟$). Since $\mathrm{T}(d,1)$ is star convex, $K$ can be computed in $𝒪({\log }^{2}K)$ rounds. And since a triangle fills an area, we have $|V(k\cdot \mathrm{T}(d,1))|=\mathrm{\Theta }(k^2)$, so we have an upper bound of $K=𝒪(\sqrt{n})$. Together, we obtain the following theorem (see Appendix C for the proof):