Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter⋆
arXiv:2604.16112v1 [cs.DC] 17 Apr 2026
Henning Hillebrandt1 , Andreas Padalkin1 , Christian Scheideler1 , Daniel Warner1 , and Julian Werthmann1 Paderborn University, Paderborn, Germany {hhilleb, padalkin, scheidel, dwarner, jwerth}@mail.upb.de
Abstract. The decomposition of complex structures into “simpler” substructures is a powerful technique with a wide range of applications. We study the computation of decompositions in the context of programmable matter. The amoebot model is a well-established model for programmable matter, which places n tiny robots called amoebots on the triangular grid. We consider the reconfigurable circuit extension of the geometric amoebot model, which allows amoebots to interconnect via so-called circuits. Amoebots can then instantaneously transmit simple beeps to all amoebots connected by the same circuit. Using reconfigurable circuits, previous papers have described a linear-time triangulation algorithm, and a logarithmic-time decomposition algorithm into so-called tunnel regions. Both algorithms only work on a restricted class of amoebot structures. In this paper, we define a decomposition into O(|H|) simple, geodesically convex regions for arbitrary amoebot structures, and show how it can compute such a decomposition in O(log n) rounds, where |H| denotes the number of holes in the amoebot structure. As a byproduct, we also improve the global maxima algorithm of Padalkin et al. (Nat. Comput., 2024) for special cases and with that also their spanning tree algorithm to O(log n) rounds w.h.p. Keywords: Programmable matter, amoebot model, reconfigurable circuits, decomposition
1
Introduction
The decomposition of complex structures into “simpler” substructures is a powerful technique with a wide range of applications. For example, decomposing a nonconvex polygon into convex subpolygons allows us to apply algorithms for collision detection of convex polygons (e.g., [33]) on any polygon. Other applications include pattern recognition [23], Minkowski sum computation [2], motion planning [24], origami folding [19], routing [17], skeleton computation [28], shape recognition [22], and shortest path computation [35]. These applications may require different properties for the simpler structures. Typical properties are simplicity (i.e., hole-freeness) [35], convexity [25], and geodesic convexity [17]. ⋆
This work has been supported by the DFG Project SCHE 1592/10-1.
2
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
Special cases of the convex decompositions include the well known trapezoidal decomposition [38] and triangulation [13]. In this paper, we investigate the computation of simple, geodesically convex decompositions in the context of programmable matter, i.e., a substance that can adaptively change its physical properties [42]. We consider systems consisting of many small, primitive particles that can communicate with each other to perform tasks on a global level. In the past, many exciting applications for programmable matter have been proposed, including self-healing materials [4] and minimally invasive surgery [32]. The geometric amoebot model [20] is an established model to study active programmable matter systems. In this model, the particles, called amoebots, are placed on an infinite triangular grid graph, where only neighboring amoebots can directly communicate with each other. Since information can only travel amoebot by amoebot, most problems have a natural lower bound of Ω(diam) where diam denotes the diameter of the structure. For that reason, we employ the reconfigurable circuit extension [22], which allows the instantaneous transmission of very simple signals to far-away amoebots along so-called circuits. Past work on this extension showed that it can enable (poly)logarithmic solutions for many problems [5,22,35,36]. Feldmann et al. [22] proposed a linear-time triangulation algorithm for a specific class of amoebot structures, and Padalkin and Scheideler [35] showed how to decompose a simple structure into so-called tunnel regions (formally defined below) in logarithmic time. Note that the former algorithm suffers from a high runtime. Further, both decompositions have restrictions on the amoebot structure. In this paper, we define a decomposition into O(|H|) simple, geodesically convex regions for arbitrary amoebot structures with |H| holes, and show how it can compute such a decomposition in O(log n) rounds. 1.1
Problem Statement and Our Contribution
Let G∆ = (V∆ , E∆ ) be the infinite regular triangular grid and let Γ = (V, E) be an arbitrary connected subgraph of G∆ . Each node of Γ represents an amoebot and each edge indicates neighboring amoebots. Let R ⊆ V . We call the maximally connected components of GV∆ \R holes, where GV∆ \R = G∆ |V∆ \R is the graph induced by V∆ \ R. There is a unique unbounded hole, which we refer to as the outer hole. All other holes of R are its inner holes and we denote the set of inner holes of R with HR . We call R a region if and only if it is connected in Γ . We call R simple if and only if HR = ∅, i.e., R contains no inner holes. We call R geodesically convex, or just convex, if and only if for each u, v ∈ R, every shortest path between u and v in Γ is completely contained within R. S A decomposition is a family R of regions R ⊆ V such that V = R∈R R. Note that we do not require the regions to be disjoint. A decomposition is geodesically convex, or just convex, if and only if each region R ∈ R is simple and convex. We consider the convex decomposition problem. We say that the amoebot structure computes a decomposition R if and only if for each region R ∈ R, each amoebot u ∈ R knows R ∩ N (u), where N (u) denotes the neighborhood of
Geodesically Convex Decomposition in Programmable Matter
3
u in Γ . The goal of the amoebot structure is to compute a convex decomposition. The main result of this paper is stated in the following theorem. Theorem 1. An amoebot structure with |H| holes computes a decomposition consisting of Θ(|H|) simple geodesic convex regions within O(log n) rounds, w.h.p.1 As a byproduct, we improve the global maxima algorithm of [36] for special cases and with that also their spanning tree algorithm to O(log n) rounds w.h.p. 1.2
Related Work
In the computational geometry community, decompositions have been extensively studied: Given an n-gon with r reflex vertices, the task is to decompose it into a minimum number of “simpler” subpolygons. The complexity of the problem depends on (i) whether the polygon has holes, (ii) whether Steiner points are allowed, and (iii) which shapes the subpolygons are allowed to have. Shapes can be, for example, convex [14], triangular [3,8,13], geodesic triangular [15,40,41], trapezoidal [6,38], star-convex [1], or monotone [29]. For simple polygons, the best known convex decomposition algorithm with Steiner points runs in time O(n3 ) [14], and without Steiner points in time O(n + r2 min{r2 , n}) [26]. For the latter case, Chazelle proposed a 13 3 -approximation algorithm that runs in time O(n log n) [12]. However, for general polygons, finding a convex decomposition with a minimum number of convex components is NP-complete [34]. For that reason, approximate convex decompositions were introduced, where some non-convex features are considered less significant and are consequentially ignored, e.g., [27,31,43]. For polygons with |H| holes, it is possible to compute a triangulation in time O(n + |H| log |H|) [11]. There is also a randomized algorithm solving the problem in expected time O(n), which is considerably simpler [3]. This matches the known lower bound of Ω(n log n) for general polygons [7]. A geodesic triangle (also called pseudo-triangle) is a polygon with exactly three convex corners. Note that any triangulation is also a geodesic triangulation (also called pseudo-triangulation). A geodesic triangulation is called pointed if and only if each vertex has an incident face with an angle larger than 180◦ . It turns out that the definition of a minimum geodesic triangulation is equivalent to the one of a pointed geodesic triangulation [41]. For simple polygons, a pointed geodesic triangulation can be computed in linear time [15,40,41], and for general polygons, in time O(n log n) [41]. The literature on graph decompositions is vast. One of the most important classes of graph decompositions is the tree decomposition (first introduced in [37], see, e.g., [9,10] for surveys), where the nodes of a graph are covered with subsets called bags, that are associated with the nodes of a tree T . The decompositions ensure that every node is in at least one bag and, for every edge, at least one bag contains both of its endpoints. Additionally, if a node appears in two bags, 1
An event holds with high probability (w.h.p.) if it holds with probability at least 1 − 1/nc where the constant c can be made arbitrarily large.
4
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
it must also appear in every bag corresponding to a tree node on the unique path in T between their corresponding tree nodes. Another important class of graph decompositions is the core decomposition (first introduced in [39], see, e.g., [30] for a recent survey). For k ∈ N, the k-core of a graph is the largest subgraph where every node has degree at least k. It can be constructed by iteratively removing nodes of degree smaller than k from the graph until it ceases to change. By construction, the (k + 1)-core of any graph is a subset of its k-core, i.e., the resulting cores form a hierarchy on the nodes based on their connectivity. The decomposition we present in this paper is closely related to a decomposition presented for square grid graphs in [17]. The authors motivate their decomposition to enable routing on a square grid graph with holes. To this end, they ensure that each of the O(|H|) node sets created by the decomposition is hole-free and what they call path-convex, i.e., for each pair of nodes in the set, at least one shortest path remains entirely inside the region. They prove that traversing the right sequence of regions yields a shortest path in square grid graphs. Their work employs a construction of [16] to extend their results to Unit Disk Graphs where nodes have arbitrary positions in R2 and are connected if and only if they have euclidean distance 1. Contrary to their approach, we focus on triangular grid graphs and show that for each node pair of the same region all shortest paths stay within that region. Moreover, we present implementation details for the amoebot model. The reconfigurable circuit extension to the geometric amoebot model was introduced by Feldmann et al. [22]. Since then, polylogarithmic solutions were proposed for various problems including leader election [22], orientation agreement [22], shape recognition [22,36], spanning trees [21,36], shape containment [5], and shortest path forests [35]. The universal shape recognition algorithm by Feldmann et al. [22] is based on a triangulation. The runtime of the triangulation depends on the shape of the amoebot structure and is linear in n in the worst case. In order to avoid a linear runtime, they abort the triangulation of the amoebot structure if it takes longer than the triangulation of the input shape. Padalkin and Scheideler [35] utilize a divide and conquer approach to construct shortest path forests within O(|H| log3 n) rounds. For that, they decompose a simple amoebot structure into tunnel regions. We will use their decomposition algorithm in our second phase (see Section 3.2). The shortest path forests decompose an amoebot structure with respect to a set of sources. However, in general, this decomposition is neither simple nor geodesically convex.
2
Preliminaries
For a triangular grid graph Γ = (VΓ , EΓ ), we define a path Π = (v0 , . . . , vk ) as a sequence of nodes with {vi , vi+1 } ∈ EΓ for all i ∈ {0, . . . , k − 1}. Slightly abusing notation, we write v ∈ Π if v ∈ {v0 , . . . , vk } and denote the length of the path by |Π| which is the number of edges of Π. If v0 = vk , Π is called a cycle. If u = v0 and v = vk , Π is called a uv-path. Further, if there is an i ∈ {1, . . . k − 1}
Geodesically Convex Decomposition in Programmable Matter y
NN
W
N
NN
E
W
E
ES
SW W
E
x
E
W
EN
NW
z
5
SS
E
S
W
SS
Fig. 1: A triangular grid graph and the corresponding portal graphs Px , Py and Pz (from left to right). The figure is adapted from [35]. s.t. w = vi , Π is called a uwv-path. For a uv-path Π and a vw-path Π ′ , we denote by Π ◦ Π ′ the path obtained by concatenating Π and Π ′ . The distance between two nodes u, v ∈ VΓ of some triangular grid graph Γ = (VΓ , EΓ ) is the number of edges on a shortest uv-path, i.e. dΓ (u, v) := minuv-path Π |Π|. We extend the distance function to sets by taking the minimum distance between two nodes. More specifically, we define for V1 , V2 ⊆ VΓ distance dΓ (V1 , V2 ) := minv1 ∈V1 , v2 ∈V2 dΓ (v1 , v2 ). We define the boundary of an (inner or outer) hole H to be the set of nodes that neighbor a node of H and call a node incident to H, if it is part of H’s boundary. A node set is incident to H, if one of its nodes is incident to H. As in previous works on decompositions of grid graphs, our construction is based on the concept of portal graphs [17,35]. For a triangular grid graph Γ = (VΓ , EΓ ), let Ex ⊆ EΓ be the set of edges parallel to the x-axis. Then, the x-portals of Γ are the connected components of the subgraph (VΓ , Ex ). For each u ∈ V , we denote the unique x-portal that contains u by portalx (u). We define y- and z-portals analogously. Two portals P1 and P2 are adjacent if there exists an edge {v1 , v2 } ∈ EΓ such that v1 ∈ P1 and v2 ∈ P2 . The x-portal graph Px = (VPx , EPx ) of Γ has a node for each x-portal of Γ . Two nodes of Px are connected by an edge if and only if the corresponding portals are adjacent. We define the y-portal graph Py and the z-portal graph Pz analogously. An example of the three portal graphs is depicted in Figure 1. The definition of portal graphs yields a notion of distances in the direction of a specific axis. For two nodes u, v ∈ VΓ , we define the x-distance dΓ,x (u, v) between u and v as the distance between portalx (u) and portalx (v) in Px . Similarly, we define dΓ,y (u, v) and dΓ,z (u, v) as the distances in Py and Pz , respectively. We conclude by restating two important lemmas from [17,35]. Lemma 1 (Adapted from [17,35]). Let Γ = (VΓ , EΓ ) be a simple triangular grid graph. Then, the portal graphs Px , Py , and Pz are trees. Lemma 2 (Adapted from [17,35]). Let Γ = (VΓ , EΓ ) be a simple triangular grid graph. Then, dΓ (u, v) = 21 (dΓ,x (u, v) + dΓ,y (u, v) + dΓ,z (u, v)) holds.
6
3
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
Convex Decomposition
In this section, we present our convex decomposition for regular triangular grid graphs. Our construction closely follows the approach of Coy et al. [17] for square grid graphs. However, since we consider triangular grid graphs, the proofs turn out to be more complicated. The general idea of the approach is to split the grid graph at certain strategic portals and nodes. All nodes involved in a split become part of all adjacent resulting regions. Our construction consists of three phases. In the first phase, we decompose the grid graph into simple regions. We call the intersection of a region and a portal at which we split the grid graph a gate. In the second phase, we split the regions further into tunnel regions, i.e., regions that intersect at most two gates. In the third phase, we divide the tunnel regions into convex regions. Throughout the paper, we frequently split triangular grid graphs along portals. In the following, we describe how we perform such splitting operations for y-portals. Splitting operations for x- and z- portals are defined analogously. An example of a splitting operation is depicted in Figure 2. Definition 1 (Splitting Operations). Let Γ = (VΓ , EΓ ) be a triangular grid graph and P be a y-portal in Γ . Further, let v1 , . . . , vℓ be nodes on P that are each adjacent to a distinct specified empty grid point. We distinguish two types of splitting operations. 1. Splitting Γ at P : We replace each node p ∈ P with two copies pWNW and pESE . Let q ∈ P and r ∈ P be the neighbors of p in P in NNE and SSW direction, if they exist, respectively. pWNW has edges to qWNW , rWNW , and to p’s neighbors in the NNW and W directions, if they exist, respectively. Analogously, pESE has edges to qESE , rESE , and to p’s neighbors in the SSE and E directions, if they exist, respectively. 2. Splitting Γ at P and v1 , . . . , vℓ : We start by splitting Γ at P as described in Case (1). Afterwards, for 1 ≤ i ≤ ℓ, if the empty gridpoint specified for vi is in the directions SSE or E from vi , we replace vESE with two copies NNE SSW NNE vESE and vESE . vESE has edges to the neighbors of vESE in the NNE and SSW E directions, if they exist, respectively. Analogously, vESE has edges to the neighbors of vESE in the SSW and SSE directions, if they exist, respectively. The case where the empty grid point specified for vi is in the directions NNW or W from vi is analogous.
3.1
Decomposition into Simple Regions
The first phase splits our grid graph into simple regions, i.e., regions without holes. For each inner hole H ∈ H of Γ we consider the WNW -most node vWNW (H) and the ESE -most node vESE (H) on the boundary of H (breaking ties by picking the NNE -most node respectively). We conduct splits at portaly (vWNW (H)) and vWNW (H) w.r.t. H, and portaly (vESE (H)) and vESE (H)
Geodesically Convex Decomposition in Programmable Matter
(a) A grid graph with a splitting portal and a splitting node.
(b) The grid graph has been cut along the splitting portal.
7
(c) The grid graph has been cut along the splitting portal and at the splitting node.
Fig. 2: A detailed depiction of the splitting operations (see Definition 1). The nodes connected by a dotted line occupy the same grid point.
H
(a) A grid graph with four holes.
(b) The result of the simple region decomposition.
(c) The blue line corresponds to S↘ for hole H.
Fig. 3: A detailed depiction of the simple region decomposition and one of the sequences S↘ used in the proof of Lemma 3. No path can cross S↘ .
w.r.t. H (see Definition 1 Case (2)). An example of the procedure is depicted in Figures 3a and 3b. We prove that the construction only creates O(|H|) regions and that the created regions are simple triangular grid graphs. Lemma 3. We decompose a triangular grid graph into at most 3|H| + 1 simple regions. Each resulting region is a triangular grid graph. Proof. Each split along a portal increases the number of regions by at most one. Splitting at the WNW -most and the ESE -most node further increases the number of regions by at most one. Thus, we increase the number of regions by at most three for each hole (two from portals and one from the splitting nodes). Consequently, the total number of regions will not exceed 3|H| + 1. To prove that the regions resulting from the procedure are simple, we argue that the splitting actions induce four sequences S↘ , S↗ , S↖ , and S↙ for each hole H ∈ H. Each sequence starts with H, followed alternatingly by splitting
8
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
portals and holes until it ends with the outer hole. We describe the construction of S↘ in detail and provide a depiction of S↘ in Figure 3c. The other sequences are defined analogously. We start by adding H to S↘ . After adding an inner hole H ′ to S↘ , we add the splitting portal portaly (vESE (H ′ )) to S↘ . After adding a splitting portal P to S↘ , we add the hole that is in the SSW direction of P ’s SSW -endpoint to S↘ . By construction, we never add a hole twice. Thus, we eventually add the outer hole to S↘ and the construction terminates. By construction, no region boundary can pass any of the sequences S↘ , S↗ , S↖ , or S↙ . Thus, no region can enclose H. As we can perform this argument for every hole, no region can enclose any hole, i.e. the regions must be simple. It remains to prove that the resulting regions are triangular grid graphs. This can only be false if two copies of the same node end up in the same region. As no path inside a region can cross any of the above sequences, however, each node copy must end up in a different region. □ Lemma 4. The construction creates at most 6|H| gates. Proof. For each hole H ∈ H we split at portaly (vWNW (H)) and vWNW (H) as well as portaly (vESE (H)) and vESE (H). For portaly (vWNW (H)), this creates at most three gates — one in the WNW direction of portaly (vWNW (H)), one in the ESE direction of portaly (vWNW (H)) and in the NNE direction of vWNW (H), one in the ESE direction of of portaly (vWNW (H)) and in the SSW direction of vWNW (H). For portaly (vESE (H)), we can argue analogously, that at most three gates are created. Note that any overlapping gates can only decrease the total number of gates. □ We conclude the section by stating an observation that we frequently use implicitly throughout the paper. Observation 1. Let R be a simple region and let P be a portal through R. If we split R at P (and possibly some nodes on P ), then the resulting regions remain simple and no region contains multiple copies of the same node. 3.2
Decomposition into Tunnel Regions
Next, we decompose each simple region into tunnel regions, i.e., regions that intersect at most two gates. We can adopt the construction used by Coy et al. [17] for square grids without any changes since it only relies on portal graphs. For the sake of completeness, we still describe the construction in the following. However, we deviate from Coy et al. and use the description by Padalkin and Scheideler [35] since we will use the techniques of the latter to compute the tunnel regions in Section 4.4. See Figure 4 for an example. Consider an arbitrary region and its portal graph Py . Since the region is simple, Py is a tree. First, we iteratively prune leaves that are not gates until each leaf is a gate. Let Py′ be the resulting portal tree. Then, we split the region at each non-gate portal in Py′ of degree at least 3.
Geodesically Convex Decomposition in Programmable Matter
9
Fig. 4: Example of splitting a simple region into tunnel regions. Initially, the region intersects the 5 orange gates. After performing a split along the blue gate and a node split at the east-most orange gate, the region is decomposed into 5 tunnel regions.
Consider one of the resulting regions and its portal tree Py′′ without the previously pruned portals. By construction, each leaf and each portal of degree at least 3 in Py′′ is a gate. We split each gate G of degree at least 2 as follows. Observe that by definition of gates, all adjacent portals of G are either on the west or east side of G. This allows us to order the adjacent portals P1 , . . . , Pℓ from north to south. Let gi denote the northernmost node of G adjacent to a node of Pi . We split the region at nodes g2 , . . . , gℓ . This splits G into ℓ gates of degree 1 in the portal tree. Since now each gate has a degree of 1, we obtain the following lemma. Lemma 5 (Adapted from [35]). We decompose a simple region that intersects k gates into Θ(k) tunnel regions. Since by Lemma 4, there are Θ(|H|) gates overall, we obtain the following result. Corollary 1. We decompose the grid graph into Θ(|H|) tunnel regions. 3.3
Decomposition into Convex Regions
In the final phase, we decompose each tunnel region into convex regions. Since the tunnel regions can take on complex shapes, there can still be pairs of nodes in the same tunnel region, such that the shortest path in the entire grid graph Γ between them leaves the tunnel and later reenters it from the other gate. The goal of this phase will be to separate those pairs of nodes by additional splits along portals. In particular, we will see that for each tunnel only a constant number of additional splits will be needed to make the tunnels convex. Consider a tunnel region T with gates G and G′ . Remember that G and G′ are portals in the y-direction. We first split T by portals in x- and z-direction that intersect G or G′ . For both directions q ∈ {x, z}, we distinguish between the following two cases (see Figures 5a to 5c for examples):
10
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann G G
P↑,z
G′
b↑,z
P↓,z
PzG bG z
b↑,x
P↑,x
P↑,x
P↓,x
b↓,x
P↓,x b↓,z
G′
b↑,x
b↓,x
′
bG z
PzG
(a) Case 1 for both q = x and q = z
′
PzG
PzG bG z
g′
′
bG z G
(b) Case 1 for q = x and case 2 for q=z
G′ ′ PxG
′ bG x ,g
Pz
′
Px
M
g
PxG bG x
(c) Case 2 for both q = x and q = z
′
Py g
(d) Splitting a region M with gates consisting of single nodes.
Fig. 5: Examples of splitting tunnel regions into convex regions. Black circles around nodes indicate the nodes g and g ′ which are interpreted as single node gates for splitting according to Definition 2. 1. If there is a q-portal that intersects both G and G′ within T , let P↑,q and P↓,q be the northernmost and southernmost of these q-portals, respectively. Then, we split T at P↑,q and P↓,q . Furthermore, in case P↑,q touches a boundary node b↑,q ̸∈ G ∪ G′ to the north of P↑,q , we split the region to the north of P↑,q at the closest such node to G. We do this symmetrically for the region below P↓,q . 2. Otherwise, let PqG be the unique q-portal intersecting G that minimizes ′ dT,q (PqG , G′ ). Analogously, let PqG be the unique q-portal intersecting G′ ′ ′ that minimizes dT,q (PqG , G). Then, we split T at PqG and PqG . Note that ′ after splitting T at (only) PqG and PqG there is a region Rq enclosed by PqG ′ and PqG . In case PqG touches a boundary node bG q ̸∈ G from the side of Rq , ′ we split Rq at the closest such node to G. Similarly, in case PqG touches a ′ ′ boundary node bG q ̸∈ G from the side of Rq , we split Rq at the closest such node to G′ . Note that if for both values of q the second case applies (see Figure 5c), there is a unique region M that intersects at least one gate on G’s side (PxG or ′ ′ PzG ) and at least one gate on G′ ’s side (PxG or PzG ). We now argue that all
Geodesically Convex Decomposition in Programmable Matter
11
resulting regions, except M , are convex. To this end, we make the following two observations. Observation 2. Let R be a region of some grid graph Γ that intersects (a) exactly one gate or (b) intersects exactly two gates that meet in an obtuse angle (i.e. the angle between the gates within R is 120◦ ). Then R is convex, as any path leaving and reentering R can be made shorter by traversing the gate(s) instead. Lemma 6. Let R be a convex region and let P be a portal through R. If we split R at P (and possibly some nodes on P ), then the resulting regions remain convex. Proof. Let R′ , R′′ ⊆ R denote the regions resulting from splitting R at P . W.l.o.g., let u, v ∈ R′ . Since R is convex, every shortest uv-path stays inside R. Now, assume that there is a shortest uv-path Π that crosses P and reenters R′ later through P . Then, this contradicts the fact that Π is a shortest path, as Π can be shortened by traversing P instead. Thus, a shortest path between u and v stays within R′ . As this is true for all nodes of R′ , R′ is convex. □ Intuitively, our construction ensures that all resulting regions, except M , are (subregions of regions that are) bordered by exactly to gates that meet in an obtuse angle, parallelograms or triangles, which are all convex. This gives the following lemma. Lemma 7. Except for region M , all resulting regions are convex. Proof. First, assume that for at least one value of q the first case applies. W.l.o.g. assume that the first case applies for q = x (the other case is analogous). Then, after splitting the tunnel at P↓,x and P↑,x in x-direction, we end up with up to 5 different regions. The region between P↓,x and P↑,x is a parallelogram and thus trivially convex. Furthermore, the region defined by gates G and P↓,x below P↓,x and the region defined by gates G′ and P↑,x above P↑,x are convex by Observation 2, as the gates intersect in an obtuse angle. Now consider the two remaining regions, that are (so far) defined by two gates that intersect in an acute angle. Both of these regions are intersected by a gate in z-direction, no matter whether q = z falls into case 1 or 2. To see why this is the case, consider one of the remaining regions, for example the region R that is defined by G and P↑,x above P↑,x . If q = z falls into case 1, then P↑,z touches a boundary node on its north-eastern side by definition, because the region between P↑,z and P↓,z encompasses all nodes with distance 0 between G and G′ in z-direction. Similarly, if q = z falls into case 2, then PzG touches a boundary node on its north-eastern side because it minimizes the distance in the z-portal graph from G to G′ by definition. Now note that in any case, one of these boundary nodes has to be inside R, because otherwise P↑,x wouldn’t connect G with G′ since T is simple. Thus, a gate in z-direction indeed splits up R. More precisely, it splits the region into up to three parts, depending on where it touches its first boundary node. The same argument can be made to show that the region defined by G′ and P↓,x below P↓,x is split up by a gate
12
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
in z-direction into up to three parts. One of these parts is a triangle and thus trivially convex. The other two parts are defined by two gates that intersect in an obtuse angle and are thus convex by Observation 2. Finally, note that adding gates along portals to already convex regions preserves convexity by Lemma 6. Therefore, all regions created are convex. The last case to consider is that for both q = x and q = z the second case ′ applies. Similarly to before, after splitting at PxG and PxG in the first step, up to 5 regions are created. The region defined by gates G and PxG below PxG and ′ ′ the region defined by gates G′ and PxG above PxG are convex by Observation 2, as the gates intersect in an obtuse angle. The remaining two regions (besides M ) are defined by two gates that intersect in an acute angle. Denote by R the region defined by G and PxG above PxG and denote by R′ the region defined by ′ ′ ′ G′ and PxG below PxG . After splitting at PzG and PzG (and ignoring PxG and ′ PxG again), we also end up with up to 5 regions. Two of them are convex by Observation 2. Note that PzG has to intersect R, because otherwise, PzG wouldn’t ′ minimize the distance in the z-portal graph to G′ as T is simple. Similarly, PzG ′ intersects R′ . Thus, after splitting up PzG and PzG at one of their nodes in the first step, R and R′ are each split up into up to three parts. As before, one of these parts is a triangle and therefore trivially convex. The other two parts are defined by two gates that intersect in an obtuse angle and are thus convex by Observation 2. Hence, all regions are convex. The only remaining region is M , which is excluded from the lemma statement. □ It remains to deal with region M , which might not yet be convex and needs further splits. To this end, let g be the closest node to G on either PxG or PzG that is in M , i.e. g := argminv∈(PxG ∩M )∪(PzG ∩M ) d(v, G). Note that if M is enclosed by both PxG and PzG , this is exactly the intersection point of PxG and PzG , and G if M is enclosed by only one of PxG or PzG , this is either bG x or bz . Analogously, ′ ′ ′ we define g := argminv∈(PxG′ ∩M )∪(PzG′ ∩M ) d(v, G ) on G ’s side. By choice of g and g ′ , we get the following crucial property: for any path between two nodes u, v ∈ M that leaves T through G and reenters T through G′ , there is a uv-path of the same length that goes via g and g ′ . Hence, we can w.l.o.g. interpret M as a tunnel region with single node gates g and g ′ and show how to split up this tunnel into convex regions, as the resulting regions remain convex even without this restriction. Furthermore, we have the following property which will be important later. Lemma 8. It is g ̸∈ G and g ′ ̸∈ G′ . Proof. We only prove that g ̸∈ G, as g ′ ̸∈ G′ can be proved analogously. W.l.o.g., let G be to the left of the tunnel region. The other case follows from symmetry. Now, assume for contradiction that g ∈ G. By definition of g, we have g ∈ G G G G G G G {bG x , bz }∪(Px ∩Pz ). Since bx , bz ̸∈ G by definition, it follows that g ∈ Px ∩Pz , G G ′ i.e. Px and Pz have to intersect on G. Now, let Rx (G ) be the region in which G′ lies after (only) splitting at PxG and let Rz (G′ ) be the region in which G′ lies after (only) splitting at PzG . Then, PxG either touches a boundary node
Geodesically Convex Decomposition in Programmable Matter
13
′ G G bG x ̸∈ G from the side of Rx (G ) or an endpoint of G lies on Px , as otherwise Px would not be the x-portal intersecting G that minimizes the x-distance to G′ . In the former case, we split at bG x and immediately get that g ̸∈ M , which is a contradiction. In the latter case, we consider two subcases. If the NNE -endpoint of G lies on PxG , then Rx (G′ ) has to lie above PxG . As the NNE -endpoint of G lies on PxG , it follows that PxG has to touch a boundary node bG x ̸∈ G from the side of Rx (G′ ). Since we split at bG x , this again implies that g ̸∈ M , which is a contradiction. Otherwise, if the SSW -endpoint of G lies on PxG , we have that the SSW -endpoint of G also lies on PzG . Then, Rz (G′ ) has to lie below PzG . As before, this implies that PzG touches a boundary node bG z ̸∈ G from the side of Rz (G′ ). Since we split at bG z , we get that g ̸∈ M , which is a contradiction. We reach a contradiction in any case and conclude that g ̸∈ G has to hold. □
For the remainder of this section, we show how to decompose the tunnel M with single node gates g and g ′ into convex regions. We do this by splitting M at the portals Px , Py and Pz , which we define in the following way (see Figure 5d for an example). Definition 2. Let M be a tunnel region with two gates g, g ′ ∈ M each consisting of a single node. For all directions q ∈ {x, y, z}, we split M as follows. Let dq := dM,q (g, g ′ ) be the q-distance between g and g ′ within M . We split M at d d the portal Pq := {v ∈ M | dq (g, v) = ⌈ 2q ⌉ ∧ dq (g ′ , v) = ⌊ 2q ⌋}. After splitting M at (only) Pq , let Rq (g) be the region in which g lies and Rq (g ′ ) be the region in which g ′ lies. In case Rq (g) = Rq (g ′ ), Pq has to touch a boundary node bq from the side of Rq (g) that lies on every shortest gg ′ -path within M . Then, we split Rq (g) at the westernmost such node on Pq . Lemma 9. The sets Px , Py and Pz form a portal in x-, y- and z-direction in the region M respectively. Furthermore, each gg ′ -path within M intersects with Px , Py and Pz . Proof. We show the statement for Px , as the other cases follow by symmetry. Consider the x-portal graph Px of M . Since M is simple, Px is a tree by Lemma 1, and therefore, there is a unique path from portalx (g) to portalx (g ′ ) in Px . Thus, all nodes v ∈ M with dx (g, v) = ⌈ d2x ⌉ and dx (g ′ , v) = ⌊ d2x ⌋ belong to the same portal Px . Moreover, any gg ′ -path within M intersects with Px , as there is a unique path from portalx (g) to portalx (g ′ ) in Px which intersects Px . □ We will now prove that the regions created by splitting M at Px , Py and Pz are indeed convex. We start off by showing that for any two nodes u, v of the same region R, a shortest path within M must also stay inside R. Lemma 10. Let u, v ∈ R for some region R ⊆ M resulting from splitting M at Px , Py and Pz . Then, dR (u, v) = dM (u, v). e that is partially outside of R but Proof. Assume there is a shortest uv-path Π e does not exit and re-enter R through the same portal, stays within M . Path Π
14
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
as such a path can be made shorter by traversing that portal. W.l.o.g. assume e exits R through portal Px at node vx and re-enters R through portal that Π e stays within M and M is simple, we can shorten Π e by Py at node vy . As Π replacing the subpath from vx to vy with the simple path from vx to vy along the e is not a shortest uv-path, portals that make up the boundary of R. Therefore, Π as it can be shortened by traversing that boundary instead of going around R. e cannot exist, any shortest uv-path within M also stays within R and it is As Π dR (u, v) = dM (u, v). □ Corollary 2. Let u, v ∈ R for some region R ⊆ M resulting from splitting M at Px , Py and Pz . Then, dR,x (u, v) = dM,x (u, v), dR,y (u, v) = dM,y (u, v) and dR,z (u, v) = dM,z (u, v). Proof. By Lemma 10, we know that there is a shortest uv-path Π within M that stays inside R. As the portals of a fixed direction traversed by any shortest path correspond to a shortest path in the respective portal graph, the existence of Π implies that there is a shortest uv-path within M using only portals in R. □ Next, we show that nodes u, v on two (possibly different) shortest gg ′ -paths within M , that are on the same side of a portal Px , Py or Pz , are not far away from each other. In particular, Corollary 3 implies that if u, v are inside the same region, then the shortest uv-path stays within that region, because any uv-path leaving and reentering tunnel M would be longer with respect to every direction. These properties will allow us to show convexity for other pairs of nodes later on. Lemma 11. Let Π, Π ′ be two shortest gg ′ -paths within M . Further, let u on Π and v on Π ′ such that both u and v are in the same region after splitting M at d (only) Pq for a q ∈ {x, y, z}. Then, dM,q (u, v) ≤ ⌈ 2q ⌉. Proof. By Lemma 9, both Π and Π ′ intersect with Pq . Further, since M is simple, the q-portal graph of M is a tree by Lemma 1. Therefore, both Π and Π ′ visit the same q-portals. We denote this sequence of q-portals as (p1 , . . . , pk−1 , Pq , pk+1 , . . . , pℓ ) where p1 = portalq (g) and pℓ = portalq (g ′ ). Note that after splitting at Pq , no node of a portal in the subsequence (p1 , . . . , pk−1 ) lies in the same region as any node of a portal in (pk+1 , . . . , pℓ ). This clearly holds if pk−1 and pk+1 lie on opposite sides of Pq , as Pq appears only once in the sequence and M is simple. Otherwise, if pk−1 and pk+1 lie on the same side of Pq , Pq has to touch a boundary node of Rq (g) that lies on Π and Π ′ . Since we split at that node, we get that pk−1 and pk+1 lie in different regions and the statement holds. Hence, portalq (u) and portalq (v) either both lie between Pq and portalq (g) or between Pq and portalq (g ′ ). From the definition of Pq , it d follows that dM,q (u, v) ≤ ⌈ 2q ⌉. □ Corollary 3. Let Π, Π ′ be two shortest gg ′ -paths within M . Further, let u on Π and v on Π ′ be nodes in the same region R ⊆ M resulting from splitting M at d Px , Py and Pz . Then, dR,x (u, v) ≤ ⌈ d2x ⌉, dR,y (u, v) ≤ ⌈ 2y ⌉ and dR,z (u, v) ≤ ⌈ d2z ⌉.
Geodesically Convex Decomposition in Programmable Matter
15
Proof. Since u, v ∈ R, both u and v are on the same sides of Px within M . By Lemma 11, it is dM,x (u, v) ≤ ⌈ d2x ⌉. As dR,x (u, v) = dM,x (u, v) by Corollary 2, the statement follows. The same argument applies for the other two distance cases. □ In order to argue about nodes v that do not lie on shortest gg ′ -paths within M , we will consider shortest gg ′ -paths that are closest to v. To characterize the structure of these paths, we prove the following two general lemmas that we will use later. Lemma 12. Let Γ = (VΓ , EΓ ) be a simple triangular grid graph, let u, v ∈ VΓ , and let Uuv be the set of nodes that are on a shortest uv-path in Γ . Then, Uuv is convex. Proof. We will prove the lemma by contradiction. Let x, y ∈ Uuv and assume that a shortest xy-path Π leaves Uuv directly after some node x′ and joins Uuv again directly before some node y ′ , while no nodes between x′ and y ′ on Π are in Uuv . Note that the boundary of Uuv consists of two shortest uv-paths Π ′ and Π ′′ . If x′ and y ′ are on the same path Π ′ , then Πxx′ ◦ Πx′ ′ y′ ◦ Πy′ ,y is shorter than Π, which contradicts Π being a shortest path. If, however, x′ is on the path Π ′ and y ′ is on the other path Π ′′ , then Π eventually has to get around ′′ ′ ′′ u or v. Then, either Πxx′ ◦ Πx′ ′ u ◦ Πuy ′ ◦ Πy ′ ,y or Πxx′ ◦ Πx′ v ◦ Πvy ′ ◦ Πy ′ ,y is shorter than Π, which again contradicts Π being a shortest path. □ Lemma 13. Given a simple triangular grid graph Γ = (VΓ , EΓ ), let a, b, v ∈ VΓ , and let Π be a shortest ab-path closest to v with the biggest number of closest points to v, i.e., for Π̂ :=
argmin Π ′ shortest ab-path
min dΓ (u, v), we obtain
u∈Π ′
Π ∈ argmax |VΠ′ ′ | Π ′ ∈Π̂
where VΠ′ ′ denotes the set of closest points to v on a path Π ′ , i.e., VΠ′ ′ := argmin dΓ (u, v). u∈Π ′
Further, let va′ := argminv′ ∈VΠ′ dΓ (v ′ , a) be the closest one of these nodes to a and let vb′ := argminv′ ∈VΠ′ dΓ (v ′ , b) be the closest one of these nodes to b. Both of the following hold: 1. All nodes of VΠ′ are continuous nodes on the same axis with endpoints va′ and vb′ . 2. Every shortest vva′ a-path is a shortest va-path and every shortest vvb′ b-path is a shortest vb-path. Proof. We start with the proof of Property (1), i.e., we prove that the nodes of VΠ′ are continuous nodes on the same axis with endpoints va′ and vb′ . We denote the nodes of VΠ′ on Π by p1 , . . . , pℓ , where ℓ = |VΠ′ |. First, we prove that the nodes of VΠ′ are on the same axis by contradiction. Assume that the nodes of VΠ′ are not on the same axis. Let B(v) := {u ∈ VΓ |
16
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
d(u, v) ≤ d(p1 , v)} be all nodes of distance at most d(p1 , v) from v in Γ . As all nodes of VΠ′ have the same distance to v and p1 ∈ VΠ′ , it is VΠ′ ⊆ B(v) and all nodes p ∈ VΠ′ lie on the boundary of B(v). Let pi , pj ∈ VΠ′ be two nodes on different axes. By definition of B(v) and since Γ is simple, for any two nodes u1 , u2 ∈ B(v) that are on different axes, there is a shortest path between u1 and u2 that goes through the interior of B(v). In particular, this holds for pi and pj . This, however, contradicts the fact that Π is a shortest ab-path closest to v, as the nodes in the interior of B(v) are closer to v than the nodes on the boundary of B(v). Thus, the nodes of VΠ′ are on the same axis. Next, we prove that the nodes of VΠ′ are continuous by contradiction. Assume that the nodes of VΠ′ are not continuous, i.e., there are two nodes pi , pj ∈ VΠ′ such that the subpath Πpi pj from pi to pj of Π has nodes not in VΠ′ . Since Π is a shortest ab-path closest to v, Πpi pj can not be in the interior of B(v). Therefore, Πpi pj leave and reenter B(v). Since the subgraph of Γ induced by B(v) is a simple subgraph of a hexagon, B(v) is convex. Therefore, all shortest paths between pi and pj stay inside B(v). This contradicts with Π being a shortest ab-path and leaving and reentering B(v). Thus, the nodes of VΠ′ are continuous. Finally, note that va′ (and vb′ ) are clearly endpoints of the subpath of the nodes of VΠ′ on Π, as they are closest to a (and b) among the nodes of VΠ′ by definition. We now prove Property (2), i.e., we show that every shortest vva′ a-path is a shortest va-path and every shortest vvb′ b-path is a shortest vb-path. We will prove the statement for any shortest vva′ a-path. The shortest vvb′ b-path-case is analogous. In the following, we refer to the nodes of Π as v = p1 , . . . , pℓ = va′ . Furthermore, set containing all nodes on a shortest av-path, S let Uav denote the e i.e. Uav := Πe shortest av-path Π. We start by proving by contradiction that Π leaves Uav at most once, i.e. there is a unique point pi ∈ Π such that pi+1 ̸∈ Uav . Assume Π would leave Uav more than once and let pi be the first leaving node. Then there would be reentering node pj with j > i s.t. pj−1 ̸∈ Uav but pj ∈ Uav . According to Lemma 12, all shortest pi pj -paths are inside Uav . Therefore, Π could be shortened by replacing its segment Πpi pj with such a shortest path. This is a contradiction to Π being a shortest path. We now call the unique point where Π leaves Uav v ′ . Our next goal is to show v ′ = va′ , i.e., to show that Π leaves Uav precisely at the closest point to v on Π which is also closest to a. To this end, we show that v ′ can not be closer to a than va′ and can not be further away from a than va′ . We start by proving the former by contradiction. Assume d(v ′ , a) < d(va′ , a). Since Π is a shortest ab-path, the next node in Π after v ′ must be closer to va′ than v ′ . As va′ is the first node closest to v on Π starting from v ′ and Π contains the most closest points to v among the paths closest to v, it must also be closer to v. Hence it is part of a shortest v ′ v-path and, since v ′ ∈ Uav , it is part of Uav . This is a contradiction to the definition of v ′ , as v ′ would not be the point where Π leaves Uav .
Geodesically Convex Decomposition in Programmable Matter
17
Assume d(v ′ , a) > d(va′ , a). By definition of va′ , the node after va′ on Π has at least the same distance to v and a larger distance to a. Therefore, it can not be part of Uav , as a shortest vva′ a-path is shorter than a va-path via that node. This, however, contradicts the definition of v ′ , as v ′ would not be the point where Π leaves Uav . Hence d(v ′ , a) = d(va′ , a). Since both v ′ and va′ are on the shortest ab-path Π, this yields v ′ = va′ . By definition of v ′ , we conclude va′ ∈ Uav , i.e. va′ is contained in the set of shortest paths from a to v. Thus, a shortest vva′ a-path is a shortest va-path. □ We are now ready to prove that the regions created by splitting M at Px , Py and Pz are convex. Coy et al. [17] exploited that in a square grid graph, for any node u inside a region R, there is a node u′g ∈ R, such that u′g is on a shortest gg ′ path closest to u within M and on a shortest ug-path. For triangular grid graphs, this property does not hold since there can be regions that are not crossed by any shortest gg ′ -path within M . Thus, such a u′g clearly cannot exist for nodes u from such a region. Moreover, even if a region R is crossed by a shortest gg ′ path Π within M , such a u′g doesn’t necessarily exist, since by Lemma 13, a shortest ug-path only connects with Π at the node closest to g among the nodes of Π closest to u. This closest node, however, might already be outside of R. Therefore, we have to explore in more detail what happens in the area between region R and where a shortest gg ′ -path meets the shortest ug- (or vg ′ -)path. Ultimately, we reach the following result, which concludes the decomposition. Lemma 14. Let R ⊆ M be a region resulting from splitting M at Px , Py and Pz . Then, R is convex. e be a uv-path that is partially outside of R. We Proof. Let u, v ∈ R and let Π e will prove that |Π| > dR (u, v) by showing that there is another path that stays e We will assume w.l.o.g. that neither g nor within R and is shorter than Π. ′ g lie in R, as this is the more interesting case. The other case can be argued analogously. e leaves R but not M . Then, as argued in Lemma 10, First, assume that Π e e > dR (u, v) in this case. Π can be shortened by staying within M . Thus, |Π| e that leave M . Furthermore, we Therefore, we only have to consider paths Π e that connect u to one of the two gates of M and v only have to consider paths Π to the other gate of M via shortest paths, as no shortest path leaves and reenters e first connects u with g on M through the same gate. W.l.o.g. assume that Π a shortest path and later reenters R to connect g ′ with v on a shortest path. Let Π and Π ′ each be a shortest gg ′ -path within M that is closest to u and v respectively and that also has the biggest number of closest points to u and v respectively. Now, let u′g be the closest node to g on Π among the nodes of Π closest to u (see Figure 6). Note that u′g ̸∈ R may hold. Further, let Π̂ be a shortest path from u to u′g that stays inside R as long as possible. By Lemma 13, we know that Π̂ ◦ Πu′g g is a shortest ug-path. Let u′ be the last node on Π̂ ◦ Πu′g g within R. Since g ̸∈ R, u′ has to lie on (at least) one of the portals Px , Py or Pz .
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann →
18
g
Pq ′
Pq ′
u ,p u′g
v Π′
Π̂
Π̂′
vg′ ′ ,v ′ ,p′
u
→ g′
→
Π g
u′g v ′
Π̂ u′
Pq
Pq ′
p
v′
Π̂ u
Π′ p′
vg′ ′ → g′
Π
Fig. 6: Examples of the notation used in the proof of Lemma 14. Region R intersects with Px = Pq and Py = Pq′ . In the top figure, both u′g , vg′ ′ ∈ R. In the bottom figure, both u′g , vg′ ′ ̸∈ R.
Let Pq with q ∈ {x, y, z} be a portal such that u′ ∈ Pq (if there is more than one such portal, pick one arbitrarily). We define analogous nodes on v’s side: let vg′ ′ be the closest node to g ′ on Π ′ among the nodes of Π ′ closest to v and let Π̂ ′ be a shortest path from v to vg′ ′ that stays inside R as long as possible. Let v ′ be the last node within R on the shortest vg-path Π̂ ′ ◦ Πv′ ′ ′ g′ . Note that v ′ has g
to lie on (at least) one of the portals Px , Py or Pz that is different from Pq , as otherwise one of the paths Π̂ ◦ Πu′g g or Π̂ ′ ◦ Πv′ ′ ′ g′ would cross Pq twice which g
contradicts them being shortest paths. Hence, let Pq′ with q ′ ∈ {x, y, z} be a portal such that v ′ ∈ Pq′ and q ̸= q ′ (if there is more than one such portal, pick one arbitrarily). We denote the remaining direction by q ′′ ∈ {x, y, z} \ {q, q ′ }. See Figure 6 for an example. With these definitions in place, we will first argue that u′ and u′g have to lie on the same side of Pq′′ . This is clearly true if u′g ∈ R, since we have u′ ∈ R by definition and all nodes of the same region lie on the same side of all portals. It remains to consider the case that u′g ̸∈ R. Let p be the node in Π ∩ Pq that
Geodesically Convex Decomposition in Programmable Matter
19
is closest to u′ . Since u′g is a closest node on Π to u and u′ is on a shortest uu′g -path, u′g is also a closest node on Π to u′ . Further, since p is the closest node to u′ in Π ∩ Pq , since Π maximizes the number of closest points to u and since M is simple, p is also a closest node on Π to u′ . Recall that by Lemma 13, the subpath Πu′g p is a straight line. This implies that Π̂u′ u′g , Πu′g p and the path between p and u′ on Pq together form an equilateral triangle. Now, assume for contradiction that u′ and u′g lie on different sides of Pq′′ , i.e. Pq′′ cuts through that triangle between u′ and u′g . Then, Π̂u′ u′g is a straight line on the q ′ -axis and Πu′g p is a straight line on the q ′′ -axis. Since Π is a shortest gg ′ -path, one of the subpaths Πgu′g and Πpg′ has to intersect Pq′′ . Let a ∈ Π ∩ Pq′′ and let b ∈ Π̂u′ u′g ∩Pq′′ . If a ∈ Πgu′g , then we can identify a shortest ap-path by traversing Pq′′ and Pq . Hence, we can replace the subpath Πap with this new path to obtain another shortest gg ′ -path. However, since b lies on this path and b is closer to u′ than u′g (and thus also closer to u than u′g ), this contradicts Π being a shortest gg ′ -path closest to u. Similarly, if a ∈ Πpg′ , we can identify a shortest u′g a-path by traversing Π̂u′g b and Pq′′ . This again yields a shortest gg ′ -path that is closer to u than Π. We reach a contradiction in both cases and conclude that indeed both u′ and u′g lie on the same side of Pq′′ . Analogously, we can argue that both v ′ and vg′ ′ lie on the same side of Pq′′ . Since both u′ , v ′ ∈ R by definition, we get that u′g and vg′ ′ lie on the same side of Pq′′ . We call this property (∆). We will now upper bound the q-, q ′ - and q ′′ -distances between u′ and v ′ in R. We begin with the q-direction. First, note that it is dM,q (u′ , g ′ ) = dM,q (p, g ′ ) d because both u′ , p ∈ Pq . Moreover, it is dM,q (p, g ′ ) ≤ ⌈ 2q ⌉ by Lemma 11 since ′ ′ both p and g lie on a shortest gg -path and are on the same side of Pq . Combining d both facts we get dM,q (u′ , g ′ ) ≤ ⌈ 2q ⌉. Altogether, we conclude: Cor. 2
dR,q (u′ , v ′ ) = dM,q (u′ , v ′ ) ≤ dM,q (u′ , g ′ ) + dM,q (g ′ , v ′ ) ≤ ⌈
dq ⌉ + dM,q (v ′ , g ′ ). 2
We bound the q ′ -distance between u′ and v ′ in R similarly. Since both v ′ , p′ ∈ d ′ Pq′ , we get dM,q′ (g, v ′ ) = dM,q′ (g, p′ ). Moreover, it is dM,q′ (g, p′ ) ≤ ⌈ 2q ⌉ by ′ ′ Lemma 11 since both p and g lie on a shortest gg -path and are on the same d ′ side of Pq′ . Combining both facts we get dM,q′ (g, v ′ ) ≤ ⌈ 2q ⌉. Altogether, we conclude: Cor. 2
dR,q′ (u′ , v ′ ) = dM,q′ (u′ , v ′ ) ≤ dM,q′ (u′ , g) + dM,q′ (g, v ′ ) ≤ dM,q′ (u′ , g) + ⌈
dq ′ ⌉. 2
Finally, for the q ′′ -distance between u′ and v ′ in R, we know by property (∆) that both u′g and vg′ ′ lie on the same side of Pq′′ . Using Lemma 11, we get: Cor. 2
dR,q′′ (u′ , v ′ ) = dM,q′′ (u′ , v ′ ) ≤ dM,q′′ (u′ , u′g ) + dM,q′′ (u′g , vg′ ′ ) + dM,q′′ (vg′ ′ , v ′ ) Lem. 11
≤
dM,q′′ (u′ , u′g ) + ⌈
We call the three inequalities above property (A).
dq′′ ⌉ + dM,q′′ (vg′ ′ , v ′ ). 2
20
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
Next, we lower bound dM (u′ , g) + dM (v ′ , g ′ ). Since u′ ∈ Pq and v ′ ∈ Pq′ , it d ′ d is dM,q (u′ , g) ≥ ⌈ 2q ⌉ and dM,q′ (v ′ , g ′ ) ≥ ⌊ 2q ⌋ by the definitions of Pq and Pq′ . We get the following lower bounds for the q- and q ′ -directions: dq ⌉ + dM,q (v ′ , g ′ ) 2 dq′ dM,q′ (u′ , g) + dM,q′ (v ′ , g ′ ) ≥ dM,q′ (u′ , g) + ⌊ ⌋ 2 dM,q (u′ , g) + dM,q (v ′ , g ′ ) ≥ ⌈
Furthermore, we know by property (∆) that one of the shortest paths Πu′g g or d ′′
Πv′ ′ ′ g′ crosses Pq′′ . Therefore, it is dM,q′′ (u′g , g) + dM,q′′ (vg′ ′ , g ′ ) ≥ ⌊ q2 ⌋ by the g
definition of Pq′′ . We get the following lower bound for the q ′′ -direction:
dM,q′′ (u′ , g) + dM,q′′ (v ′ , g ′ ) = dM,q′′ (u′ , u′g ) + dM,q′′ (u′g , g) + dM,q′′ (v ′ , vg′ ′ )+ dM,q′′ (vg′ ′ , g ′ ) ≥ dM,q′′ (u′ , u′g ) + ⌊
dq′′ ⌋ + dM,q′′ (v ′ , vg′ ′ ) 2
We call the three inequalities above property (B). e M of Π e inside M : Plugging it all together, we get for the part Π e M | ≥ dM (u, g) + dM (v, g ′ ) |Π = dR (u, u′ ) + dM (u′ , g) + dR (v, v ′ ) + dM (v ′ , g ′ ) (B),Lem. 2 1 dq ≥ dR (u, u′ ) + dR (v, v ′ ) + ⌈ ⌉ + dM,q (v ′ , g ′ )+ 2 2 dq ′ ′ dM,q′ (u , g) + ⌊ ⌋+ 2 dq′′ ′ ′ dM,q′′ (u , ug ) + ⌊ ⌋ + dM,q′′ (vg′ ′ , v ′ ) 2 1 dq ′ ′ ′ ′ = dR (u, u ) + dR (v, v ) + ⌈ ⌉ + dM,q (v , g )+ 2 2 dq ′ dM,q′ (u′ , g) + ⌈ ⌉ − 1[dq′ odd] + 2 dq′′ ′ ′ dM,q′′ (u , ug ) + ⌈ ⌉ − 1[dq′′ odd] + 2 dM,q′′ (vg′ ′ , v ′ )
= dR (u, u′ ) + dR (v, v ′ ) +
−
1 dq ⌈ ⌉ + dM,q (v ′ , g ′ )+ 2 2 dq ′ dM,q′ (u′ , g) + ⌈ ⌉+ 2 dq′′ ′ ′ dM,q′′ (u , ug ) + ⌈ ⌉ + dM,q′′ (vg′ ′ , v ′ ) 2 1[dq′ odd] + 1[dq′′ odd] 2
Geodesically Convex Decomposition in Programmable Matter (A)
≥ dR (u, u′ ) + dR (v, v ′ ) + −
Lem.2
=
1 dR,q (u′ , v ′ ) + dR,q′ (u′ , v ′ ) + dR,q′′ (u′ , v ′ ) 2 1[dq′ odd] + 1[dq′′ odd] 2
dR (u, u′ ) + dR (v, v ′ ) + dR (u′ , v ′ ) −
≥ dR (u, v) −
21
1[dq′ odd] + 1[dq′′ odd]
1[dq′ odd] + 1[dq′′ odd]
2
2
e inside M . By Lemma 8, we know Note that we lower bounded the part of Π ′ that the distance between g and g outside of M is at least 2. Hence, we have e ≥ |Π e M | + 2 > dR (u, v). We conclude that R is indeed convex. |Π| □
4
Implementation in the Amoebot Model
In this section, we show how we compute the convex decomposition in the geometric amoebot model [18,20] with reconfigurable circuits [22], which we describe in Section 4.1. In Sections 4.2 and 4.3, we introduce algorithms from previous work that we will use as subroutines. Finally, in Section 4.4, we present our convex decomposition algorithm. 4.1
Geometric Amoebot Model with Reconfigurable Circuits
We now formally introduce the geometric amoebot model. We will explain the model to a level of detail that is sufficient to understand the results of this paper. For all other (unused) features of the model, e.g., movements, we refer to [18,20]. The model places a set of n anonymous finite state machines called amoebots with constant memory on the infinite regular triangular grid graph G∆ = (V∆ , E∆ ). Each amoebot occupies one node and every node is occupied by at most one amoebot. We assume that all amoebots have the same compass orientation (it defines one of its incident edges in G∆ as the eastern direction) and chirality.2 Let the amoebot structure VΓ ⊆ V∆ be the set of nodes occupied by the amoebots. By abuse of notation, we identify amoebots with their nodes. We assume that GΓ = (VΓ , EΓ ) is connected, where GΓ = G|VΓ is the graph induced by VΓ . We utilize the reconfigurable circuit extension by Feldmann et al. [22] as our communication model. In this extension, each edge between two neighboring amoebots u and v is replaced by c edges called external links with endpoints called pins, for some constant c ≥ 1 that is the same for all amoebots. For each of these links, one pin is owned by u while the other pin is owned by v. In this paper, we assume that neighboring amoebots have a common labeling of their incident external links. 2
This is reasonable under the considered communication model since Feldmann et al. [22] showed that all amoebots are able to quickly come to an agreement.
22
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
Each amoebot u partitions its pin set P (u) into a collection C(u) S of pairwise disjoint subsets such that the union equals the pin set, i.e., P (u) = C∈C(u) C. We call S C(u) the pin configuration of u and C ∈ C(u) a partition set of u. Let C = u∈S C(u) be the collection of all partition sets in the system. Two partition sets are connected if and only if there is at least one external link between those sets. Let L be the set of all connections between the partition sets in the system. Then, we call H = (C, L) the pin configuration of the system and any connected component C of H a circuit. An amoebot is part of a circuit if and only if the circuit contains at least one of its partition sets. A priori, an amoebot u may not know whether two of its partition sets belong to the same circuit or not since initially it only knows C(u). Each amoebot u can send a primitive signal (a beep) via any of its partition sets C ∈ C(u) that is received by all partition sets of the circuit containing C at the beginning of the next round. The amoebots are able to distinguish between beeps arriving at different partition sets. More specifically, an amoebot receives a beep at partition set C if at least one amoebot sends a beep on the circuit belonging to C, but the amoebots neither know the origin of the signal nor the number of origins. We assume the fully synchronous activation model, i.e., the time is divided into synchronous rounds, and every amoebot is active in each round. On activation, each amoebot may update its state, reconfigure its pin configuration, and activate an arbitrary number of its partition sets. The beeps are propagated on the updated pin configurations. The time complexity of an algorithm is measured by the number of synchronized rounds required by it.
4.2
Subroutines from Prior Work
In this section, we list algorithms from previous work on the model that we will use as a blackbox in our decomposition algorithm. Theorem 2 (Adapted from [36]). Let C1 , . . . , Cm be sets of candidates such that each set Ci is connected by a unique circuit Ci . The amoebot structure can elect a leader from each set of candidates within Θ(log n) rounds w.h.p. Remark 1. We can use Theorem 2 to elect leaders in a portal graph by selecting a representative for each portal, e.g., the northermost amoebot of each y-portal. Theorem 3 (Adapted from [36]). An amoebot structure can determine for each boundary set whether it is an inner boundary set or an outer boundary set within O(log n) rounds w.h.p. Padalkin and Scheideler proposed various tree primitives utilizing reconfigurable circuits. They have also shown how an amoebot structure can simulate these on portal trees.
Geodesically Convex Decomposition in Programmable Matter
23
Theorem 4 (Adapted from [35]). Let P = (VP , EP ) be a portal tree. Let R ∈ VP . Then, the PASC algorithm lets each portal P ∈ VP compute distances d(R, P ) and m = maxP ′ ∈VP d(R, P ′ ) within O(log m) = O(log n) rounds.3 Theorem 5 (Adapted from [35]). Let P = (VP , EP ) be a portal tree. Let Q ⊆ VP and R ∈ Q. Then, the root and prune primitive roots P at R and prunes all subtrees without a portal in Q within O(log |Q|) = O(log n) rounds. Finally, we list methods for portals and regions which were also introduced by Padalkin and Scheideler. Lemma 15 (Adapted from [35]). Let P = (VP , EP ) be a portal tree. Let deg(P ) denote the degree of P . Let c be a constant. Then, each portal P can check whether deg(P ) ≥ c within O(min{c, log degP (P )}) = O(1) rounds. Lemma 16 (Adapted from [35]). Let R ⊆ VΓ be a connected subset, e.g., a region or a portal. Let S ⊆ VΓ . Then, region R can determine whether S ∩ R ̸= ∅ within O(1) rounds. Lemma 17 (Adapted from [35]). Let P be a portal. Let S ⊆ P be a nonempty set of amoebots and u ∈ P one of the endpoints of the portal. Then, we can compute the closest amoebot v ∈ S to u in O(1) rounds. 4.3
Global Maxima
Let d be a cardinal direction and let R ⊆ VΓ be a non-empty set of amoebots. We call argminw∈R f d (R, w) the global maxima of R in direction d where f d (R, w) denotes the number of amoebots in R that lie in direction d from amoebot w. Theorem 6 (Adapted from [36]). The amoebot structure can compute the global maxima of R within O(log2 n) rounds w.h.p. The idea of their algorithm is to first elect an arbitrary reference amoebot u ∈ R, then apply a spatial version of the PASC algorithm to compute the distance to that reference amoebot with respect to the cardinal direction d and finally apply a consensus algorithm to determine the amoebots with the maximal distance. However, the PASC algorithm computes the distances from the least significant bit to the most significant bit while the consensus algorithm requires the distances from the most significant bit to the least significant bit. Since the amoebots cannot store their distances, they have to recompute the distances for each iteration of the consensus algorithm. We can improve the runtime for boundary sets as follows. First, we apply Theorem 2 to split the boundary cycle into a chain. Then, we apply the block 3
Note that in general a portal is not able to store its distance since amoebots only have constant sized memory. Hence, the computation happens in iterations. In each iteration, each portal computes a single bit of the two distances. We are still able to perform simple operations in an online fashion, e.g., comparisons and bit shifts (in order to divide by 2) [5].
24
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
primitive of [36] to divide the chain into blocks of length Θ(log n). Next, each block applies Theorem 6 to compute its global maxima in R. Let M ⊆ R denote the set of all global maxima of all blocks. Finally, we apply Theorem 6 to compute the global maxima of M . However, each amoebot in M now stores its distance in its block such that we do not need to recompute the distances for each iteration of the consensus algorithm. Theorem 7. A boundary set can compute the global maxima of R within O(log n) rounds w.h.p. Proof. If an amoebot is a global maximum of R, then it is also a global maximum of its block. Hence, the final application of the global maxima algorithm also computes the global maxima of R. Note that each block is able to store the distance since it has Θ(log n) amoebots. If a block has more than one global maxima, they must have the same distance such that each block has to only store one distance. By Theorem 2, the splitting of the boundary cycle into a chain requires O(log n) rounds w.h.p. The block primitive requires O(log n) rounds. We refer to [36] for the details. Since the blocks have size Θ(log n), the first application of Theorem 6 requires O(log2 log n) = O(log n) rounds w.h.p. Since we do not have to recompute for each iteration of the consensus algorithm, the second application of Theorem 6 requires O(log n) rounds w.h.p. Overall, the algorithm requires O(log n) rounds w.h.p. □ Remark 2. Theorem 7 immediately improves the runtime of the spanning tree algorithm of Padalkin et al. [36] to O(log n) rounds w.h.p. If R is connected, the global maxima must be on the outer boundary. Hence, Theorems 3 and 7 imply the following corollary. Corollary 4. If R is connected, the amoebot structure can compute the global maxima of R within O(log n) rounds w.h.p. 4.4
Convex Decomposition
In this section, we show how an amoebot structure can compute the convex decomposition described in Section 3. Decomposition into Θ(|H|) simple regions First, each boundary set determines whether it is an inner or outer boundary set (see Theorem 3). Second, each inner boundary set computes the NNE -most amoebot of the WNW -most amoebots and the NNE -most amoebot of the ESE -most amoebots (see Theorem 7). Let S denote the set of amoebots computed by the inner boundary sets. Third, each y-portal P determines whether S ∩ P ̸= ∅ (see Lemma 16). Let P = {P ∈ VPy | S ∩ P ̸= ∅}. We split the amoebot structure at each portal in P and each amoebot in S.
Geodesically Convex Decomposition in Programmable Matter
25
Lemma 18. An amoebot structure computes a decomposition consisting of Θ(|H|) simple regions within O(log n) rounds w.h.p. Proof. The correctness follows from Lemma 3, and the runtime follows from Theorems 3 and 7 and lemma 16. □ Decomposition into Θ(|H|) simple tunnel regions We apply the decomposition algorithm by Padalkin and Scheideler [35]. For the sake of completeness, we outline the algorithm in the following. First, each region applies a leader election on the gates it intersects (see Theorem 2 and remark 1). This allows us to apply the root and prune primitive to prune all subtrees without a gate (see Theorem 5). Then, we split the region at all non-gate portals of degree at least 3 (see Lemma 15). Finally, we split each gate of degree at least 2 as follows. The gate marks the northernmost amoebot adjacent to each adjacent portal. Note that each amoebot can locally decide whether it is one of these amoebots. Then, the gate removes the northernmost marked amoebot and splits the region at the remaining marked amoebots (see Lemma 17). Lemma 19 (Adapted from [35]). Given a decomposition consisting of Θ(|H|) simple regions, an amoebot structure computes a decomposition consisting of Θ(|H|) simple tunnel regions within O(log n) rounds w.h.p. Decomposition into Θ(|H|) simple, geodesically convex regions First, each tunnel region that intersects two gates applies a leader election on the gates it intersects (see Theorem 2 and remark 1). Let G be the elected gate and G′ the other one. Let portalq (S) = {portalq (u) | u ∈ S} for a set S of amoebots. Now, for q ∈ {x, z}, each q-portal determines whether it is in portalq (G) or portalq (G′ ) (see Lemma 16) and shares this information with adjacent portals. This allows portals P↑,q and P↓,q to identify themselves if they exist. If they exist, they identify b↑,q (b↓,q ) by determining their westernmost northern (southern) boundary amoebot that is not on G or G′ (see Lemma 17). If they do not exist, i.e., portalq (G) and portalq (G′ ) are disjoint, we compute ′ G Pq and PqG as follows. Consider the q-portal graph Pq of the region. Since the tunnel region is simple, Pq is a tree. Let Qq = portalq (G ∪ G′ ). Let Rq ∈ Qq be the northernmost portal in portalq (G). We apply the root and prune ′ primitive on Pq with Qq and Rq (see Theorem 5). This allows PqG (PqG ) to identify itself since it is the only gate in portalq (G) (portalq (G′ )) with a neighbor ′ G′ not in portalq (G) (portalq (G′ )). PqG (PqG ) identifies bG q (bq ) by determining its ′ westernmost boundary amoebot that is not on G (G ) (see Lemma 17). Next, the whole tunnel region checks whether P↑,x /P↓,x , or P↑,z /P↓,z exist (see Lemma 16). If at least one pair of portals exists, Case 1 holds for q = x, q = z, or both so that we terminate (see Figure 5). Otherwise, Case 2 holds for both, q = x and q = z, and we proceed as follows. First, M identifies itself ′ ′ by checking whether it is intersected by both, PxG ∪ PzG and PxG ∪ PzG (see ′ G Lemma 16). Then, g (g ) identifies itself. It is either the intersection of Px and
26
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann ′
′
′
′
G G G PzG (PxG and PzG ), bG x (bx ), or bz (bz ). Note that only one of these cases can hold at the same time. For q ∈ {x, y, z}, we apply the root and prune algorithm on Pq with Q = {portalq (g), portalq (g ′ )} and R = portalq (g) (see Theorem 5). Note that since |Q| = 2, we obtain a path of portals. We get dq = dq (portalq (g), dq (portalq (g ′ ))) = maxP ∈Pq d(portalq (g), P ) = maxP ∈Pq d(portalq (g ′ ), P ). Hence, we use the PASC algorithm with portalq (g) (portalq (g ′ )) as the root to compute the values dq , dq (portalq (g), P ) and dq (portalq (g ′ ), P ) for each portal P (see Theorem 4). Each portal P compares their distances to dq /2. This allows portal Pq to identify itself. ′ T Finally,Slet Pq = (VPq′ , EPq′ ) denote the pruned portal tree. Then, SM = q∈{x,y,z} P ∈VP ′ P denotes the set of all amoebots that are on a shortest path q
between g and g ′ [35]. Note that each amoebot can determine whether it is in SM since it knows whether it is on a portal of Pq′ . It can also determine whether its removal would disconnect SM , which implies that all shortest paths between g and g ′ within M go through it. Let Bq denote the set of all these amoebots. For q ∈ {x, y, z}, we check whether Rq (g) = Rq (g ′ ) (see Lemma 16). If this is the case, portal Pq identifies amoebot bq by computing the westernmost amoebot of Bq ∩ Pq (see Lemma 17). Lemma 20. Given a decomposition consisting of Θ(|H|) simple tunnel regions, an amoebot structure computes a decomposition consisting of Θ(|H|) simple convex regions within O(log n) rounds w.h.p. Proof. The correctness follows from Lemma 7, and the runtime follows from Theorems 2, 4 and 5 and lemmas 16 and 17. □ Combining Lemmas 18 to 20 proves Theorem 1.
5
Conclusion and Future Work
We have shown how to decompose general regular triangular grid graphs into simple, geodesically convex regions and how to compute such a decomposition in the amoebot model with reconfigurable circuits in logarithmic time. Notably, the decomposition is model-independent and might be of broader interest beyond the amoebot model. While our focus has been on the decomposition problem itself, prior work suggests that a wide range of problems can benefit from such decompositions (e.g. motion planning). Exploring these applications remains an interesting direction for future work. Acknowledgements. We thank Dona Davis, Anns Mary Francis, and Alex Poovathummoottil Sibichen for their contributions to an early draft of the paper.
References 1. Abrahamsen, M., Blikstad, J., Nusser, A., Zhang, H.: Minimum star partitions of simple polygons in polynomial time. TheoretiCS 5 (2026)
Geodesically Convex Decomposition in Programmable Matter
27
2. Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of minkowski sums. Comput. Geom. 21(1-2), 39–61 (2002) 3. Amato, N.M., Goodrich, M.T., Ramos, E.A.: A randomized algorithm for triangulating a simple polygon in linear time. Discret. Comput. Geom. 26(2), 245–265 (2001) 4. An, S., Yoon, S.S., Lee, M.W.: Self-healing structural materials. Polymers 13(14), 2297 (2021) 5. Artmann, M., Padalkin, A., Scheideler, C.: On the shape containment problem within the amoebot model with reconfigurable circuits. In: DISC. LIPIcs, vol. 356, pp. 7:1–7:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2025) 6. Asano, T., Asano, T., Imai, H.: Partitioning a polygonal region into trapezoids. J. ACM 33(2), 290–312 (1986) 7. de Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational geometry: algorithms and applications, 3rd Edition. Springer (2008) 8. Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Computing in Euclidean geometry, pp. 47–123. World Scientific (1995) 9. Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations i. upper bounds. Inf. Comput. 208(3), 259–275 (2010). https://doi.org/10.1016/J.IC.2009.03.008, https://doi.org/10.1016/j.ic.2009.03.008 10. Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations II. lower bounds. Inf. Comput. 209(7), 1103–1119 (2011). https://doi.org/10.1016/J.IC.2011. 04.003, https://doi.org/10.1016/j.ic.2011.04.003 11. Chan, T.M.: Triangulating a polygon with holes in optimal (deterministic) time. CoRR abs/2603.21617 (2026) 12. Chazelle, B.: A theorem on polygon cutting with applications. In: FOCS. pp. 339– 349. IEEE Computer Society (1982) 13. Chazelle, B.: Triangulating a simple polygon in linear time. Discret. Comput. Geom. 6, 485–524 (1991) 14. Chazelle, B., Dobkin, D.P.: Optimal convex decompositions. In: Machine Intelligence and pattern recognition, vol. 2, pp. 63–133. Elsevier (1985) 15. Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L.J., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12(1), 54–68 (1994) 16. Coy, S., Czumaj, A., Feldmann, M., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P., Struijs, M.: Near-shortest path routing in hybrid communication networks. CoRR abs/2202.08008 (2022), https://arxiv.org/abs/2202.08008 17. Coy, S., Czumaj, A., Scheideler, C., Schneider, P., Werthmann, J.: Routing schemes for hybrid communication networks. Theor. Comput. Sci. 985, 114352 (2024) 18. Daymude, J.J., Richa, A.W., Scheideler, C.: The canonical amoebot model: algorithms and concurrency control. Distributed Comput. 36(2), 159–192 (2023) 19. Demaine, E.D., Demaine, M.L., Mitchell, J.S.B.: Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami. Comput. Geom. 16(1), 3–21 (2000) 20. Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: amoebot - a new model for programmable matter. In: SPAA. pp. 220–222. ACM (2014) 21. Emek, Y., Gil, Y., Harlev, N.: On the power of graphical reconfigurable circuits. In: DISC. LIPIcs, vol. 319, pp. 22:1–22:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024) 22. Feldmann, M., Padalkin, A., Scheideler, C., Dolev, S.: Coordinating amoebots via reconfigurable circuits. J. Comput. Biol. 29(4), 317–343 (2022)
28
H. Hillebrandt, A. Padalkin, C. Scheideler, D. Warner and J. Werthmann
23. Feng, H.F., Pavlidis, T.: Decomposition of polygons into simpler components: Feature generation for syntactic pattern recognition. IEEE Trans. Computers 24(6), 636–650 (1975) 24. Hert, S., Lumelsky, V.J.: Polygon area decomposition for multiple-robot workspace division. Int. J. Comput. Geom. Appl. 8(4), 437–466 (1998) 25. Keil, J.M.: Decomposing a polygon into simpler components. SIAM J. Comput. 14(4), 799–817 (1985) 26. Keil, J.M., Snoeyink, J.: On the time bound for convex decomposition of simple polygons. Int. J. Comput. Geom. Appl. 12(3), 181–192 (2002) 27. Lien, J., Amato, N.M.: Approximate convex decomposition of polygons. Comput. Geom. 35(1-2), 100–123 (2006) 28. Lien, J., Keyser, J., Amato, N.M.: Simultaneous shape decomposition and skeletonization. In: Symposium on Solid and Physical Modeling. pp. 219–228. ACM (2006) 29. Liu, R., Ntafos, S.C.: On decomposing polygons into uniformly monotone parts. Inf. Process. Lett. 27(2), 85–89 (1988) 30. Malliaros, F.D., Giatsidis, C., Papadopoulos, A.N., Vazirgiannis, M.: The core decomposition of networks: theory, algorithms and applications. VLDB J. 29(1), 61– 92 (2020). https://doi.org/10.1007/S00778-019-00587-4, https://doi.org/ 10.1007/s00778-019-00587-4 31. Mamou, K., Ghorbel, F.: A simple and efficient approach for 3d mesh approximate convex decomposition. In: ICIP. pp. 3501–3504. IEEE (2009) 32. Montemagno, C., Bachand, G.: Constructing nanomechanical devices powered by biomolecular motors. Nanotechnology 10(3), 225 (1999) 33. O’Rourke, J., Chien, C., Olson, T., Naddor, D.: A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19(4), 384–391 (1982) 34. O’Rourke, J., Supowit, K.J.: Some np-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181–189 (1983) 35. Padalkin, A., Scheideler, C.: Polylogarithmic time algorithms for shortest path forests in programmable matter. In: PODC. pp. 65–75. ACM (2024) 36. Padalkin, A., Scheideler, C., Warner, D.: The structural power of reconfigurable circuits in the amoebot model. Nat. Comput. 23(4), 603–625 (2024) 37. Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986). https://doi.org/10.1016/0196-6774(86) 90023-4, https://doi.org/10.1016/0196-6774(86)90023-4 38. Seidel, R.: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. 1, 51– 64 (1991) 39. Seidman, S.B.: Network structure and minimum degree. Social networks 5(3), 269– 287 (1983) 40. Speckmann, B., Tóth, C.D.: Allocating vertex pi-guards in simple polygons via pseudo-triangulations. Discret. Comput. Geom. 33(2), 345–364 (2005) 41. Streinu, I.: Pseudo-triangulations, rigidity and motion planning. Discret. Comput. Geom. 34(4), 587–635 (2005) 42. Toffoli, T., Margolus, N.: Programmable matter: Concepts and realization. Int. J. High Speed Comput. 5(2), 155–170 (1993) 43. Wei, X., Liu, M., Ling, Z., Su, H.: Approximate convex decomposition for 3d meshes with collision-aware concavity and tree search. ACM Trans. Graph. 41(4), 42:1– 42:18 (2022)