We study centralized reconfiguration problems for geometric amoebot structures. A set of n amoebots occupy nodes on the triangular grid and can reconfigure via expansion and contraction operations. We focus on the joint movement extension, where amoebots may expand and contract in parallel, enabling coordinated motion of larger substructures. Prior work introduced this extension and analyzed reconfiguration under additional assumptions such as metamodules. In contrast, we investigate the intrinsic dynamics of reconfiguration without such assumptions by restricting attention to centralized algorithms, leaving distributed solutions for future work. We study the reconfiguration problem between two classes of amoebot structures A and B: For every structure S∈A, the goal is to compute a schedule that reconfigures S into some structure S′∈B. Our focus is on sublinear-time algorithms. We affirmatively answer the open problem by Padalkin et al. (Auton. Robots, 2025) whether a within-the-model sublinear-time universal reconfiguration algorithm is possible, by proving that any structure can be reconfigured into a canonical line-segment structure in O(nlogn) rounds. Additionally, we give a constant-time algorithm for reconfiguring any spiral structure into a line segment. These results are enabled by new constant-time primitives that facilitate efficient parallel movement. Our findings demonstrate that the joint movement model supports sublinear reconfiguration without auxiliary assumptions. A central open question is whether universal reconfiguration within this model can be achieved in polylogarithmic or even constant time.
Figures & tables
Figure 1: Amoebot model and axes. The black nodes and edges indicate the nodes and edges occupied by amoebots. The red edges indicate bonds between the amoebots. The gray edges indicate the triangular grid GΔ . We omit the grid in all other figures.
Figure 2: Movements. The yellow amoebot in (a) and (c) indicates amoebot c . The blue amoebot in (b) and (c) indicates amoebot x .
Figure 3: Results. Classes with a thicker frame indicate canonical classes. Red arrows point to superclasses and with that indicate trivial solutions. Note that we do not depict all superclasses. Black arrows indicate results by Padalkin et al. [ 14 ] . Note that their superconstant algorithms simulate algorithms from [ 5 , 12 ] . They define rhombical and hexagonal metamodules. Rhombical ( Hexagonal ) contains all amoebot structure that consist of rhombical (hexagonal) metamodules. RhombicalLine ( HexagonalLine ) contains all amoebot structure forming a line of rhombical (hexagonal) metamodules. Ring contains canonical amoebot structures forming a ring (see [ 5 ] for details). m denotes the number of metamodules. Blue edges indicate our results. Note that our algorithm that reconfigures bounded structures into histograms simulates an algorithm from [ 4 ] .
Figure 4: Tunneling primitive. In each round, adjacent amoebots of the same color perform a handover. The gray node is unoccupied. In all figures, a simple arrow between two subfigures indicates the execution of the first step of a round (i.e., the removal of bonds) after establishing the adjacency closure, and a double arrow the execution of the second step of a round (i.e., the movements) unless stated otherwise. Note that only the fully completed rounds (i.e., both steps were executed) count to the total number of rounds.
Figure 5: Shearing primitive. The blue amoebots indicate the connection points. The yellow area indicates the triangle within the primitive is performed from the perspective of the bottom connection points.
Figure 6: Parallelogram primitive. The blue amoebots indicate the connection points.
Figure 7: First phase of the triangle primitive. The blue amoebots indicate the connection points.
Figure 8: Second phase of the triangle primitive on a triangle of side length ℓ=17 . Note that k=4 holds. The blue amoebots indicate the connection points.
Figure 9: Third phase of the triangle primitive. The blue amoebots indicate the connection points. The first two and last two double arrows indicate 2 rounds.
Figure 10: Fourth phase of the triangle primitive. The blue amoebots indicate the connection points.
Figure 11: Trapezoid primitive. The orange node/amoebot indicates the starting point. The blue amoebots indicate the connection points. Each double arrow indicates a phase consisting of 2 rounds.
Figure 12: Preprocessing phase of the Monotone2LineSegment algorithm.
Figure 13: Rules used in the Monotone2LineSegment algorithm.
Figure 14: State graph. The termination state is not shown. Any other state has an edge to the termination state.
Figure 15: Rule 4. We omit the first phase, i.e., the application of Rule 3d (see Figure 13 ), and only show the second and third phase.
Figure 16: Histograms in a star-convex structures. The yellow amoebot indicates the center amoebot. The blue amoebots indicate the connection points used by the Histogram2LineSegment algorithm. The yellow triangles indicate the area for each instance from which no amoebot is moved out, respectively. The double arrow indicates multiple rounds.
Figure 17: First phase of the Arbitrary2Bounded algorithm. The amoebot structure has n=49 . Hence, each pair of rows that we want to merge has at least one row with less than n=7 amoebots. The blue amoebots indicate the pairs of amoebots that are unable to expand.
Figure 18: Single iteration of the second phase of the Arbitrary2Bounded algorithm. The blue amoebots indicate a pair of amoebots that were unable to expand in the first phase. The gray nodes are initially adjacent to the participating amoebots.
Figure 19: Third phase of the Arbitrary2Bounded algorithm. All amoebots contract again.
Figure 20: Combing algorithm by Aloupis et al. [ 4 ] . The blue amoebots indicate the sweep line.
Figure 21: Unrolling algorithm. The blue amoebots indicate the corners in the initial amoebot structure. The double arrow indicates a phase consisting of 2 rounds.
Figure 22: Base line construction. The blue amoebots indicate the left and right corners. The green path indicates the base line. The yellow areas indicate the parallelograms. The orange areas indicate the areas where parallelograms intersect. Each double arrow indicates multiple rounds.
Figure 23: Alignment of the z -segments. The blue amoebots indicate the amoebots on the base line connected to a z -segment of an arm. The green path indicates the base line. The yellow areas indicate the shearing primitive. The second double arrow indicates 2 rounds.
Figure 24: Alignment of the x -segments. The blue amoebots indicate all left and right corners on the base line and all corners in the arms. The green path indicates the base line. The yellow areas indicate the shearing primitive. The second double arrow indicates 2 rounds.
Institute of AI and Robotics, Academy for Engineering & Technology, Fudan University, Shanghai 200433, China · Department of Mechanical Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong SAR, China