Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2307.04385 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929238388506624 |
|---|---|
| author | Almalki, Nada Gupta, Siddharth Michail, Othon |
| author_facet | Almalki, Nada Gupta, Siddharth Michail, Othon |
| contents | In this paper, we explore how geometric structures can be grown exponentially fast. The studied processes start from an initial shape and apply a sequence of centralized growth operations to grow other shapes. We focus on the case where the initial shape is just a single node. A technical challenge in growing shapes that fast is the need to avoid collisions caused when the shape breaks, stretches, or self-intersects. 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(k\log 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 $Ω(k\log k)$ time steps to be grown. If nodes can additionally be connected as soon as they become adjacent, we prove that if a shape $S$ has a spanning tree with $O(k)$ turning points on every root-to-leaf path, then the adjacency closure of $S$ can be grown in $O(k \log n)$ time steps. In the strongest model that we study, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_04385 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Exponential Growth of Geometric Shapes Almalki, Nada Gupta, Siddharth Michail, Othon Data Structures and Algorithms Computational Geometry Robotics In this paper, we explore how geometric structures can be grown exponentially fast. The studied processes start from an initial shape and apply a sequence of centralized growth operations to grow other shapes. We focus on the case where the initial shape is just a single node. A technical challenge in growing shapes that fast is the need to avoid collisions caused when the shape breaks, stretches, or self-intersects. 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(k\log 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 $Ω(k\log k)$ time steps to be grown. If nodes can additionally be connected as soon as they become adjacent, we prove that if a shape $S$ has a spanning tree with $O(k)$ turning points on every root-to-leaf path, then the adjacency closure of $S$ can be grown in $O(k \log n)$ time steps. In the strongest model that we study, 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. |
| title | On the Exponential Growth of Geometric Shapes |
| topic | Data Structures and Algorithms Computational Geometry Robotics |
| url | https://arxiv.org/abs/2307.04385 |