DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2025.20

Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits

Authors: Nada Almalki, Siddharth Gupta, Othon Michail, and Andreas Padalkin

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

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.

Cite as

Nada Almalki, Siddharth Gupta, Othon Michail, and Andreas Padalkin. Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 20:1-20:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{almalki_et_al:LIPIcs.SAND.2025.20,
  author =	{Almalki, Nada and Gupta, Siddharth and Michail, Othon and Padalkin, Andreas},
  title =	{{Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{20:1--20:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.20},
  URN =		{urn:nbn:de:0030-drops-230730},
  doi =		{10.4230/LIPIcs.SAND.2025.20},
  annote =	{Keywords: growth process, shrinking process, collision avoidance, programmable matter}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2024.23

Brief Announcement: On the Exponential Growth of Geometric Shapes

Authors: Nada Almalki, Siddharth Gupta, and Othon Michail

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

We explore how geometric structures (or shapes) can be grown exponentially fast from a single node, through a sequence of centralized growth operations, and if collisions during growth are to be avoided. We identify a parameter k, representing the number of turning points within specific parts of a shape. We prove that, if edges can only be formed when generating new nodes and cannot be deleted, trees having O(k) turning points on every root-to-leaf path can be grown in O(klog n) time steps and spirals with O(log n) turning points can be grown in O(log n) time steps, n being the size of the final shape. For this case, we also show that the maximum number of turning points in a root-to-leaf path of a tree is a lower bound on the number of time steps to grow the tree and that there exists a class of paths such that any path in the class with Ω(k) turning points requires Ω(klog k) time steps to be grown. In the stronger model, where edges can be deleted and neighbors can be handed over to newly generated nodes, we obtain a universal algorithm: for any shape S it gives a process that grows S from a single node exponentially fast.

Cite as

Nada Almalki, Siddharth Gupta, and Othon Michail. Brief Announcement: On the Exponential Growth of Geometric Shapes. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 23:1-23:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{almalki_et_al:LIPIcs.SAND.2024.23,
  author =	{Almalki, Nada and Gupta, Siddharth and Michail, Othon},
  title =	{{Brief Announcement: On the Exponential Growth of Geometric Shapes}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{23:1--23:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.23},
  URN =		{urn:nbn:de:0030-drops-199015},
  doi =		{10.4230/LIPIcs.SAND.2024.23},
  annote =	{Keywords: centralized algorithm, growth process, collision, programmable matter}
}

Search Results

Documents authored by Almalki, Nada

Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits

Abstract

Cite as

Brief Announcement: On the Exponential Growth of Geometric Shapes

Abstract

Cite as

Thanks for your feedback!

Could not send message