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 edge-connected configuration of n squares into any other using at most O(n2) sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require ω(n2) sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side 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. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The O( Pn) bound never exceeds O(n2), and is optimal (up to constant factors) among all bounds parameterized by just n and P. 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 arrive at a single solid xy-monotone component. 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, on all types of square configurations.


    Access

    Download


    Export, share and cite



    Title :

    Compacting Squares:Input-Sensitive In-Place Reconfiguration of Sliding Squares



    Publication date :

    2022-06-01


    Remarks:

    Akitaya , H A , Demaine , E D , 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 . in A Czumaj & Q Xin (eds) , Proceedings of 18 th Scandinavian Symposium and Workshops on Algorithm Theory . , 4 , Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , Leibniz International Proceedings in Informatics, LIPIcs , vol. 227 , 18 th Scandinavian Symposium and Workshops on Algorithm Theory , Torshavn , Faroe Islands , 27/06/2022 . https://doi.org/10.4230/LIPIcs.SWAT.2022.4



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629