2026-07-21T19:38:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23073 2025-10-02T12:33:04Z ddc:004 open_access

Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits Almalki, Nada Gupta, Siddharth Michail, Othon Padalkin, Andreas growth process shrinking process collision avoidance programmable matter In this paper, we study the problem of efficiently reducing geometric shapes into other such shapes in a distributed setting through size-changing operations. We develop distributed algorithms using the reconfigurable circuit model to enable fast node-to-node communication. Let n denote the number of nodes and k the number of turning points in the initial shape. We show that the system of nodes can reduce itself from any tree to a single node using only shrinking operations in O(k log n) rounds w.h.p. and any tree to its incompressible form in O(log n) rounds given prior knowledge of the incompressible nodes, or O(k log n) without it, w.h.p. We also give an algorithm to transform any tree to a topologically equivalent tree in O(k log n+log² n) rounds w.h.p. using both shrinking and growth operations. On the negative side, we show that one cannot hope for o(log² n)-round transformations for all shapes of Θ(log n) turning points. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nada Almalki and Siddharth Gupta and Othon Michail and Andreas Padalkin 2025 Is Part Of LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2025.20 urn:nbn:de:0030-drops-230730 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode