Optimal In-Place Compaction of Sliding Cubes

Onderzoeksoutput: Bijdrage aan congresPaperAcademic

47 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's20:1
Aantal pagina's20
StatusGepubliceerd - mrt. 2024
Evenement40th European Workshop on Computational Geometry (EuroCG 2024) - Ioannina, Griekenland
Duur: 13 mrt. 202415 mrt. 2024

Congres

Congres40th European Workshop on Computational Geometry (EuroCG 2024)
Land/RegioGriekenland
StadIoannina
Periode13/03/2415/03/24

Vingerafdruk

Duik in de onderzoeksthema's van 'Optimal In-Place Compaction of Sliding Cubes'. Samen vormen ze een unieke vingerafdruk.

Citeer dit