Akitaya, H., Demaine, E., Korman, M., Kostitsyna, I., Parada, I., Sonke, W., Speckmann, B., Uehara, R., & Wulms, J. (2022). Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares [Conference Presentation]. 38th European Workshop on Computational Geometry, Italy. https://doi.org/10.34726/3466
E192-01 - Forschungsbereich Algorithms and Complexity E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Date (published):
2022
-
Event name:
38th European Workshop on Computational Geometry
en
Event date:
14-Mar-2022 - 16-Mar-2022
-
Event place:
Italy
-
Keywords:
Sliding Squares
en
Abstract:
Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one such configuration of n squares into any other using O(n2) sliding moves, while maintaining connectivity. For certain pairs of configurations, reconfiguration may require Ω(n2) sliding moves. However, significantly fewer moves may be sufficient. We present Gather&Compact, an input-sensitive in-place algorithm that requires only O(Pn) sliding moves to transform one configuration into the other, where ̄P is the maximum perimeter of the two bounding boxes. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally make it xy-monotone. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin.
en
Project title:
Human-Centered Algorithm Engineering: P31119-N31 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
-
Project (external):
Vienna Science and Technology Fund (WWTF) Independent Research Fund Denmark grant 2020-2023
-
Project ID:
ICT19-035 9131-00044B
-
Additional information:
This is an extended abstract of a presentation given at EuroCG’22. It has been made public for the benefit of the community and should be considered a preprint rather than a formally reviewed paper. Thus, this work is expected to appear eventually in more final form at a conference with formal proceedings and/or in a journal.