On the Diameter of Arrangements of Topological Disks

Abstract

Let $\mathcal{D}=\{D_0,\dots ,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 ${\Delta }_{ij}$ be the number of connected components of $D_i\cap D_j$, and let $\Delta :={\max }_{i,j}{\Delta }_{ij}$. We show that the diameter of ${\mathcal{G}}^{\ast }$, the dual graph of $\mathcal{A}$, can be bounded as a function of $n$ and $\Delta$. 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 $\Delta$. In particular, for the case of two disks, we prove that the diameter of ${\mathcal{G}}^{\ast }$ is at most $\max \{2,2\Delta \}$ and this bound is tight. For the general case of $n>2$ disks, we show that the diameter of ${\mathcal{G}}^{\ast }$ is $O(n^3{2}^n\Delta )$. 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\Delta )$. To this end, we first show that the number of maximum faces -- faces whose ply is $n$ -- is $O(n^2\Delta )$; the latter bound, which is of independent interest, is tight in the worst case.