Optimal In-Place Compaction of Sliding Cubes

Research output: Contribution to conferencePaperAcademic

8 Downloads (Pure)

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 two dimensions and any dimension higher than three.
Original languageEnglish
Pages20:1
Number of pages20
Publication statusPublished - Mar 2024
Event40th European Workshop on Computational Geometry (EuroCG 2024) - Ioannina, Greece
Duration: 13 Mar 202415 Mar 2024

Conference

Conference40th European Workshop on Computational Geometry (EuroCG 2024)
Country/TerritoryGreece
CityIoannina
Period13/03/2415/03/24

Fingerprint

Dive into the research topics of 'Optimal In-Place Compaction of Sliding Cubes'. Together they form a unique fingerprint.

Cite this