@inproceedings{ffb6b5974e4345a68ac52d9548cb979e,
title = "Optimal In-Place Compaction of Sliding Cubes",
abstract = "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.",
keywords = "Modular robots, Reconfiguration algorithm, Sliding cubes",
author = "Irina Kostitsyna and Ophelders, {Tim A.E.} and Irene Parada and Tom Peters and Sonke, {Willem M.} and Bettina Speckmann",
year = "2024",
month = may,
day = "31",
doi = "10.4230/LIPIcs.SWAT.2024.31",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "31:1--31:14",
editor = "Bodlaender, {Hans L.}",
booktitle = "19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024",
note = "19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 ; Conference date: 12-06-2024 Through 14-06-2024",
}