Abstract 1 Introduction 2 Algorithm and complexity 3 Contributed media References

Sliding Cubes in Parallel

Hugo A. Akitaya ORCID Miner School of Computer and Information Sciences, University of Massachusetts Lowell, MA, USA    Joseph Dorfer ORCID Institute of Algorithms and Theory, Graz University of Technology, Austria    Peter Kramer ORCID Department of Computer Science, TU Braunschweig, Germany    Christian Rieck ORCID Institute of Mathematics, University of Kassel, Germany    Soham Samanta Greater Commonwealth Virtual School, Medford, MA, USA    Gabriel Shahrouzi ORCID Miner School of Computer and Information Sciences, University of Massachusetts Lowell, MA, USA    Frederick Stock ORCID Miner School of Computer and Information Sciences, University of Massachusetts Lowell, MA, USA
Abstract

The sliding cubes model serves as a well-established theoretical framework for formalizing and analyzing reconfiguration algorithms in modular robotic systems built from face-connected cubic modules. We extend the parallel sliding cubes model from two to three dimensions, presenting new algorithms, surprising complexity results, and a generalization of the best known bounds from two to three dimensions. A companion video visualizes and explains our results.

Keywords and phrases:
Sliding squares, parallel motion, reconfigurability, three dimensions, constant makespan, log-APX hardness, 𝖭𝖯-hardness, worst-case optimality
Category:
Media Exposition
Funding:
Joseph Dorfer: Austrian Science Fund (FWF) 10.55776/DOC183.
Peter Kramer: Partially funded by a fellowship of the German Academic Exchange Service (DAAD) and the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant 530918134.
Christian Rieck: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant 522790373.
Copyright and License:
[Uncaptioned image] © Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Soham Samanta,
Gabriel Shahrouzi, and Frederick Stock; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Computational geometry
Related Version:
Based on: https://doi.org/10.48550/arXiv.2603.08537 [1]
Funding:
Hugo A. Akitaya, Gabriel Shahrouzi, and Frederick Stock: Supported by the National Science Foundation (NSF), grant CCF-2348067.
DOI:
10.4230/LIPIcs.SoCG.2026.96
Event:
42nd International Symposium on Computational Geometry (SoCG 2026)
Editors:
Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Programmable matter systems are composed of large numbers of simple modules that are capable of autonomously reconfiguring their collective shape. These systems have attracted significant attention for applications in robotics, manufacturing, and distributed computing. In practice, identifying reconfiguration sequences that transform one connected configuration into another while preserving connectivity and avoiding collisions is a highly nontrivial algorithmic problem. We consider the Sliding Cubes model introduced by Fitch, Butler, and Rus [5], where identical modules move via discrete moves in a three-dimensional lattice. Modules can perform two types of move, a slide or a convex transition, as shown in Figure 1. A slide translates the module by one unit along the surface of two adjacent modules, while a convex transition displaces it along the surface of only one module along two axes.

Figure 1: Two types of legal move, (i) slide and (ii) convex transition.

Our work considers the coordinated parallel motion of unit cubes in the three-dimensional integer grid, following and extending the notation of [2]. Parallel moves are performed in discrete transformations with unit-time duration; as in the two-dimensional model [2], both types of move take unit time to complete and occur at a fixed, constant speed. Transformations must preserve a connected backbone which requires moving modules to be free: moving modules do not provide connectivity. A set of modules M is free in a configuration C if the removal of any subset of M from C leaves a connected configuration. In addition, transformations must not induce collisions, in which the volume of two modules overlap. For instance, modules thus cannot trade places during a transformation or perform a convex transition through the same cell. We refer to [2] and Figure 2 for details.

Figure 2: Examples of collisions. Figure from [2], used with the authors’ permission.

2 Algorithm and complexity

In this media exposition, we illustrate and interactively visualize three main results. All technical details of the complexity results as well as the algorithm that are presented in the accompanying video to this abstract are given in the full version [1].

  1. 1.

    Deciding the minimum makespan for Parallel Sliding Cubes is para-NP-hard when parameterized by the makespan and symmetric difference size: There is no polynomial time algorithm even for the case in which both values are constant (unless 𝖯=𝖭𝖯).

  2. 2.

    The makespan minimization problem in both Parallel and Sequential Sliding Cubes is log-APX-hard and cannot be approximated by a factor better than Θ⁢(log⁡n).

  3. 3.

    Schedules for universal reconfiguration of makespan 𝒪⁢(A+h) can be computed in polynomial time, where A is the area of the projection of the configuration onto the base of its bounding box and h is the height of the bounding box. In the worst case this input-sensitive bound becomes 𝒪⁢(n) which is worst-case optimal.

Parameterized complexity.

To prove para-NP-hardness, the full paper reduces from the 𝖭𝖯-hard problem 3Sat, which asks whether a given Boolean formula φ is satisfiable [3]. The reduction constructs two configurations, illustrated in Figure 3, using gadgets that encode the variables (blue) and clauses (green) of φ. These gadgets are connected by connectors (yellow), and the two configurations differ by a single module (black/transparent) at one end. Solving the instance in a single transformation requires a continuous path of modules to move between the two endpoints without disconnecting the structure, forcing the transformation to encode an assignment satisfying φ.

Refer to caption
(a)
Refer to caption
(b)
(c)
Refer to caption

(d)
Refer to caption

(e)
Figure 3: The construction for φ=(x1∨x3∨x4)∧(x1∨x2∨x3)∧(x1¯∨x2¯∨x4¯)∧(x2¯∨x3¯∨x4¯) is shown in (a). In (b), a solution is illustrated (moving modules deleted). Variable gadgets are placed in ascending order left to right. In (c)–(e) we show the connector gadget and possible paths.

Inapproximability.

The full paper shows log-APX-hardness by reduction from Set Cover [4]. An instance of this problem defines k sets S={s1,…,sk} over [n]={1,…,n} such that ⋃i=1ksi=[n] and asks for a minimum cardinality subset S⋆⊆S with ⋃si∈S⋆si=[n]. The construction has a bounding box of size 𝒪⁢(n4⁢k7) for an instance with n elements and k sets; a schematic example is shown in Figure 4.

Figure 4: A diagram showing our construction for the Set Cover instance with n=3 over the sets s1={1,2,3}, s2={2,3}, and s3={1,3}. Indicated is a schedule representing S⋆={s2,s3}.

A worst-case optimal algorithm.

At a high level, the algorithm generalizes the methods given in [2] for two dimensions to three dimensions. The approach proceeds in three phases: (1) Gather, (2) Compress, and (3) Compact Reconfiguration. The goal of (1) Gather is to form a snake, which is informally a connected sequence of 5×5×5 metamodules. Intuitively, the snake can move freely through the configuration without disrupting the connectivity of the remaining modules. As it moves, it collects non-cut modules, growing in size until it is sufficiently large to initiate the second phase. At a high level, in (2) Compress the snake collects the remaining modules of the configuration, creating a compact configuration. A configuration C is compact if for every module u∈C, the cuboid defined by the position of u and the origin is entirely contained in the configuration:

∀u∈C:∀a∈[0,x(u)]:∀b∈[0,y(u)]:∀c∈[0,z(u)]:(a,b,c)∈C.

The (3) Compact Reconfiguration phase deals with arbitrary reconfiguration of these.

3 Contributed media

To assist with developing an intuitive understanding of key pieces from the algorithm and hardness gadgets, we created visualizations of them. An interactive form of these will be hosted online using the WebVis111https://modular-robotics-group.github.io/modular-robotics/WebVis/index.html tool created by the UML Modular Robotics group and presented in [6]. We implemented new features for the tool to facilitate the creation of manual animations of reconfiguration sequences. We have compiled these implementations into an accompanying video for a presentation during CG week, similar to [7] which appeared at CG week 2024.

References

  • [1] Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Gabriel Shahrouzi, and Frederick Stock. Sliding cubes in parallel, 2026. doi:10.48550/arXiv.2603.08537.
  • [2] Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding squares in parallel. In European Symposium on Algorithms (ESA), pages 28:1–28:17, 2025. doi:10.4230/LIPIcs.ESA.2025.28.
  • [3] Mark de Berg and Amirali Khosravi. Optimal binary space partitions for segments in the plane. International Journal on Computational Geometry and Applications, 22(3):187–206, 2012. doi:10.1142/S0218195912500045.
  • [4] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing (STOC), pages 624–633, 2014. doi:10.1145/2591796.2591884.
  • [5] Robert Fitch, Zack J. Butler, and Daniela L. Rus. Reconfiguration planning for heterogeneous self-reconfiguring robots. In International Conference on Intelligent Robots and Systems (IROS), pages 2460–2467, 2003. doi:10.1109/IROS.2003.1249239.
  • [6] UML Modular Robotics Group, Hugo A. Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock. Finding shortest reconfiguration sequences for modular robots. In Symposium on Computational Geometry (SoCG), pages 85:1–85:5, 2025. doi:10.4230/LIPIcs.SoCG.2025.85.
  • [7] Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal in-place compaction of sliding cubes. In Symposium on Computational Geometry (SoCG), pages 89:1–89:4, 2024. doi:10.4230/LIPIcs.SoCG.2024.89.