[{"status":"public","volume":1085,"user_id":"55557","_id":"66838","publisher":"Elsevier BV","citation":{"short":"I. Kostitsyna, D. Liedtke, C. Scheideler, Theoretical Computer Science 1085 (2026).","chicago":"Kostitsyna, Irina, David Liedtke, and Christian Scheideler. “Distributed Rhombus Formation of Sliding Squares.” <i>Theoretical Computer Science</i> 1085 (2026). <a href=\"https://doi.org/10.1016/j.tcs.2026.116196\">https://doi.org/10.1016/j.tcs.2026.116196</a>.","apa":"Kostitsyna, I., Liedtke, D., &#38; Scheideler, C. (2026). Distributed rhombus formation of sliding squares. <i>Theoretical Computer Science</i>, <i>1085</i>, Article 116196. <a href=\"https://doi.org/10.1016/j.tcs.2026.116196\">https://doi.org/10.1016/j.tcs.2026.116196</a>","ieee":"I. Kostitsyna, D. Liedtke, and C. Scheideler, “Distributed rhombus formation of sliding squares,” <i>Theoretical Computer Science</i>, vol. 1085, Art. no. 116196, 2026, doi: <a href=\"https://doi.org/10.1016/j.tcs.2026.116196\">10.1016/j.tcs.2026.116196</a>.","ama":"Kostitsyna I, Liedtke D, Scheideler C. Distributed rhombus formation of sliding squares. <i>Theoretical Computer Science</i>. 2026;1085. doi:<a href=\"https://doi.org/10.1016/j.tcs.2026.116196\">10.1016/j.tcs.2026.116196</a>","bibtex":"@article{Kostitsyna_Liedtke_Scheideler_2026, title={Distributed rhombus formation of sliding squares}, volume={1085}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2026.116196\">10.1016/j.tcs.2026.116196</a>}, number={116196}, journal={Theoretical Computer Science}, publisher={Elsevier BV}, author={Kostitsyna, Irina and Liedtke, David and Scheideler, Christian}, year={2026} }","mla":"Kostitsyna, Irina, et al. “Distributed Rhombus Formation of Sliding Squares.” <i>Theoretical Computer Science</i>, vol. 1085, 116196, Elsevier BV, 2026, doi:<a href=\"https://doi.org/10.1016/j.tcs.2026.116196\">10.1016/j.tcs.2026.116196</a>."},"intvolume":"      1085","article_type":"original","date_updated":"2026-08-25T05:37:47Z","publication_status":"published","author":[{"first_name":"Irina","last_name":"Kostitsyna","full_name":"Kostitsyna, Irina"},{"id":"55557","full_name":"Liedtke, David","last_name":"Liedtke","first_name":"David"},{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"}],"publication_identifier":{"issn":["0304-3975"]},"title":"Distributed rhombus formation of sliding squares","year":"2026","doi":"10.1016/j.tcs.2026.116196","language":[{"iso":"eng"}],"article_number":"116196","abstract":[{"lang":"eng","text":"The sliding square model is a widely used abstraction for studying self-reconfigurable robotic systems, where modules are square-shaped robots that move by sliding or rotating over one another. In this paper, we propose a novel distributed algorithm that enables a group of modules to reconfigure into a rhombus shape, starting from an arbitrary side-connected configuration. It is connectivity-preserving and operates under minimal assumptions: one leader module, common chirality, constant memory per module, and visibility and communication restricted to immediate neighbors. Unlike prior work, which relaxes the original sliding square move-set, our approach uses the unmodified move-set, addressing the additional challenge of handling locked configurations. Our algorithm is sequential in nature and operates with a worst-case time complexity of O(n^2) rounds, which is optimal for sequential algorithms. To improve runtime, we introduce two parallel variants of the algorithm. Both rely on a spanning tree data structure, allowing modules to make decisions based on local connectivity. Our experimental results show a significant speedup for the first variant, and a linear average runtime for the second variant, which is worst-case optimal for parallel algorithms."}],"publication":"Theoretical Computer Science","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"keyword":["modular robots","distributed algorithms","sliding squares"],"type":"journal_article","date_created":"2026-08-25T05:30:39Z"}]