2026-07-23T18:55:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20071 2024-05-31T13:11:12Z ddc:004 open_access

Optimal In-Place Compaction of Sliding Cubes 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. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we present an in-place algorithm that 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. This result is asymptotically optimal and strictly improves on all prior work. Furthermore, our algorithm directly extends to dimensions higher than three. 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 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.31 urn:nbn:de:0030-drops-200713 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode