2026-08-17T05:07:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20034 2024-06-06T06:21:17Z ddc:004 open_access

Optimal In-Place Compaction of Sliding Cubes (Media Exposition) Kostitsyna, Irina Ophelders, Tim Parada, Irene Peters, Tom Sonke, Willem Speckmann, Bettina Sliding cubes Reconfiguration algorithm Modular robots The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. This note accompanies a video that explains our in-place algorithm for reconfiguration in the sliding cubes model. Specifically, our algorithm [Irina Kostitsyna et al., 2023] reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. As is common in the literature, we can then reconfigure between two arbitrary shapes via their canonical configurations. The number of moves performed by our algorithm is asymptotically worst-case optimal and strictly improves upon the current state-of-the-art. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irina Kostitsyna and Tim Ophelders and Irene Parada and Tom Peters and Willem Sonke and Bettina Speckmann 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.89 urn:nbn:de:0030-drops-200347 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.89 eng https://creativecommons.org/licenses/by/4.0/legalcode