Back to Search
Start Over
Optimal In-Place Compaction of Sliding Cubes
- Publication Year :
- 2023
-
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. The best algorithm currently known for the reconfiguration problem, by Abel and Kominers [arXiv, 2011], uses O(n3) moves to transform any n-cube configuration into any other n-cube configuration. As is common in the literature, this algorithm reconfigures the input into an intermediate canonical shape. In this paper 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. Furthermore, our algorithm directly extends to dimensions higher than three.
- Subjects :
- Computer Science - Computational Geometry
Computer Science - Robotics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2312.15096
- Document Type :
- Working Paper