Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.18012 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914382134378496 |
|---|---|
| author | Abiad, Aida Aronov, Boris de Berg, Mark Golak, Julian Grigoriev, Alexander van Lent, Freija |
| author_facet | Abiad, Aida Aronov, Boris de Berg, Mark Golak, Julian Grigoriev, Alexander van Lent, Freija |
| contents | Let $\mathcal{D}=\{D_0,\ldots,D_{n-1}\}$ be a set of $n$ topological disks in the plane and let $\mathcal{A} := \mathcal{A}(\mathcal{D})$ be the arrangement induced by $\mathcal{D}$. For two disks $D_i,D_j\in\mathcal{D}$, let $Δ_{ij}$ be the number of connected components of $D_i\cap D_j$, and let $Δ:= \max_{i,j} Δ_{ij}$. We show that the diameter of $\mathcal{G}^*$, the dual graph of $\mathcal{A}$, can be bounded as a function of $n$ and $Δ$. Thus, any two points in the plane can be connected by a Jordan curve that crosses the disk boundaries a number of times bounded by a function of $n$ and $Δ$. In particular, for the case of two disks, we prove that the diameter of $\mathcal{G}^*$ is at most $\max\{2,2Δ\}$ and this bound is tight.
For the general case of $n>2$ disks, we show that the diameter of $\mathcal{G}^*$ is $O(n^3 2^n Δ)$. We achieve this by proving that the number of maximal faces in $\mathcal{A}$ -- faces whose ply is more than the ply of their neighboring faces -- is $O(n^2 2^n Δ)$. To this end, we first show that the number of maximum faces -- faces whose ply is $n$ -- is $O(n^2Δ)$; the latter bound, which is of independent interest, is tight in the worst case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18012 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Diameter of Arrangements of Topological Disks Abiad, Aida Aronov, Boris de Berg, Mark Golak, Julian Grigoriev, Alexander van Lent, Freija Combinatorics Computational Geometry 68U05, 05C85 (Primary) F.2.2; G.2.1 Let $\mathcal{D}=\{D_0,\ldots,D_{n-1}\}$ be a set of $n$ topological disks in the plane and let $\mathcal{A} := \mathcal{A}(\mathcal{D})$ be the arrangement induced by $\mathcal{D}$. For two disks $D_i,D_j\in\mathcal{D}$, let $Δ_{ij}$ be the number of connected components of $D_i\cap D_j$, and let $Δ:= \max_{i,j} Δ_{ij}$. We show that the diameter of $\mathcal{G}^*$, the dual graph of $\mathcal{A}$, can be bounded as a function of $n$ and $Δ$. Thus, any two points in the plane can be connected by a Jordan curve that crosses the disk boundaries a number of times bounded by a function of $n$ and $Δ$. In particular, for the case of two disks, we prove that the diameter of $\mathcal{G}^*$ is at most $\max\{2,2Δ\}$ and this bound is tight. For the general case of $n>2$ disks, we show that the diameter of $\mathcal{G}^*$ is $O(n^3 2^n Δ)$. We achieve this by proving that the number of maximal faces in $\mathcal{A}$ -- faces whose ply is more than the ply of their neighboring faces -- is $O(n^2 2^n Δ)$. To this end, we first show that the number of maximum faces -- faces whose ply is $n$ -- is $O(n^2Δ)$; the latter bound, which is of independent interest, is tight in the worst case. |
| title | On the Diameter of Arrangements of Topological Disks |
| topic | Combinatorics Computational Geometry 68U05, 05C85 (Primary) F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2510.18012 |