Search Results

Documents authored by Almalki, Nada


Document
Brief Announcement
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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail