On the Diameter of Arrangements of Topological Disks
Aida Abiad, Boris Aronov, Mark de Berg, Julian Golak, Alexander Grigoriev, Freija van Lent · 2025
Read On the Diameter of Arrangements of Topological Disks by Aida Abiad, Boris Aronov, Mark de Berg, Julian Golak, Alexander Grigoriev, Freija van Lent (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18012.txt.
Introduction
Aida Abiad, with five co-authors, bounds how many region crossings any path needs in a plane covered by overlapping disks. The disks are topological, so their shapes can be wild, and two disks may meet in many separate pieces. The dual graph of the arrangement turns the geometry into a network whose diameter is the target.
For two disks the bound is exact and tight. For many disks the diameter grows with the disk count and the overlap count in a stated form. A key step counts faces with the deepest stacking. Geometry readers get a clean link between overlap mess and travel cost.
Catalog record
| CREATOR | Aida Abiad, Boris Aronov, Mark de Berg, Julian Golak, Alexander Grigoriev, Freija van Lent |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-18012
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Diameter of Arrangements of Topological Disks Aida Abiad, Boris Aronov, Mark de Berg, Julian Golak, Alexander Grigoriev, Freija van Lent Abstract Let 𝒟 = { D 0 , … , D n − 1 } \mathcal{D}=\{D_{0},\ldots,D_{n-1}\} be a set of n 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 ∈ 𝒟 D_{i},D_{j}\in\mathcal{D} , let Δ i j \Delta_{ij} be the number of connected components of D i ∩ D j D_{i}\cap D_{j} , and let Δ := max i , j Δ i j \Delta:=\max_{i,j}\Delta_{ij} . We show that the diameter of 𝒢 ∗ \mathcal{G}^{*} , the dual graph of 𝒜 \mathcal{A} , can be bounded as a function of n 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 n and Δ \Delta . In particular, for the case of two disks we prove that the diameter of 𝒢 ∗ \mathcal{G}^{*} is at most max { 2 , 2 Δ } \max\{2,2\Delta\} and this bound is tight. For the general case of n > 2 n>2 disks, we show that the diameter of 𝒢 ∗ \mathcal{G}^{*} is at most 2 n ( Δ + 1 ) n ( n − 1 ) / 2 min { n , Δ + 1 } 2n(\Delta+1)^{n(n-1)/2}\min\{n,\Delta+1\} . We achieve this by proving that the number of maximal faces in 𝒜 \mathcal{A} — the faces whose ply is more than the ply of their neighboring faces — is at most n ( Δ + 1 ) n ( n − 1 ) / 2 n(\Delta+1)^{n(n-1)/2} , which is interesting in its own right. Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands and Department of Mathematics and Data Science, Vrije Universiteit Brussel, [email protected]://orcid.org/0000-0003-4003-4291Supported by the Dutch Research Council (NWO) through the grants VI.Vidi.213.085 and OCENW.KLEIN.475. Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY, [email protected]://orcid.org/0000-0003-3110-4702Partially supported by NSF Grant CCF-20-08551. Department of Mathematics and Computer Science, TU Eindhoven, the [email protected]://orcid.org/0000-0001-5770-3784Supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Institute of Sustainable Logistics and Mobility and Institute of Operations Management, University of Hamburg, Hamburg, [email protected]://orcid.org/0000-0003-2626-5819 Department of Data Analytics and Digitalisation, Maastricht University, the [email protected]://orcid.org/0000-0002-8391-235X Department of Data Analytics and Digitalisation, Maastricht University, the [email protected]://orcid.org/0000-0002-6417-9199 ccs Theory of computation Computational geometry ccs Mathematics of computing Graphs and surfaces ccs Mathematics of computing Geometric topology keywords Topological disk, arrangement, face, Jordan curve, crossing † † runningauthor: A. Abiad, B. Aronov, M. de Berg, J. Golak, A. Grigoriev, and F. van Lent † † copyright: Aida Abiad, Boris Aronov, Mark de Berg, Julian Golak, Alexander Grigoriev, and Freija van Lent 1 Introduction The arrangement \mathcal{A}(S) defined by a set S of objects in the plane is the subdivision of the plane into faces, edges, and vertices induced by (the boundaries of) the objects. Arrangements in the plane and in higher dimensions play a fundamental role in computational geometry, since many geometric problems can be transformed into problems on arrangements. As a result, the combinatorial complexity of arrangements—the total number of vertices, edges, and faces (and higher-dimensional features)—induced by various types of objects has been studied extensively. These studies concern the complexity of complete arrangements as well as the complexity of various substructures: single cells, many cells, zones, levels, and so on; see the book by Sharir and Agarwal [ 7 ] or the surveys by Agarwal and Sharir [ 1 ] or Halperin and Sharir [ 5 ] . The known results on arrangements typically deal with constant-complexity objects such as lines, circles, or other objects whose boundaries intersect a bounded number of times. This is not surprising, as the complexity of the arrangement induced by some set of objects obviously cannot be bounded if we do not put a bound on the number of intersections between the boundaries of any two objects in the set. In this paper we are interested in whether anything meaningful can be said about complexity of an arrangement if the number of boundary intersections of any two objects in the arrangement is not necessarily bounded. Let \mathcal{D}=\{D_{0},\ldots,D_{n-1}\} be a set of n topological disks in \mathbb{R}^{2} . To simplify the presentation we will refer to the objects in \mathcal{D} as disks , but the reader should keep on mind that the boundaries of the disks in \mathcal{D} are arbitrary closed Jordan curves. In particular, the boundaries \partial D_{i} and \partial D_{j} of two disks D_{i},D_{j}\in\mathcal{D} can intersect arbitrarily many times. We will assume that the disks in \mathcal{D} are in general position . More precisely, we assume that \partial D_{i}\cap\partial D_{j} consists of finitely many points, that two boundaries properly cross every time they intersect, i.e., there are no tangencies, and that no three disk boundaries have a point in common. Let \mathcal{A}:=\mathcal{A}(\mathcal{D}) be the arrangement induced by \mathcal{D} . Let \Delta_{ij} denote the number of connected components of the intersection D_{i}\cap D_{j} of a pair of objects D_{i},D_{j}\in\mathcal{D} , and define \Delta:=\max_{i,j}\Delta_{ij} . We refer to \Delta as the overlap number of \mathcal{D} . Note that the complexity of \mathcal{A} cannot be bounded as a function of n and \Delta . Indeed, even for n=2 and \Delta=1 , the number of faces in \mathcal{A} can be arbitrarily large, as illustrated in Figure 1 (i). Figure 1 : (i) A set of two topological disks with \Delta=1 can induce an arrangement with arbitrarily many faces. (ii) A set of three topological disks and the dual graph of their arrangement. The arrangement has four maximal faces, whose dual nodes are shown in black. The edges incident to the node corresponding to the unbounded face are only drawn partially, to avoid cluttering the figure. If the blue disk is D_{0} , the red disk is D_{1} , and the green disk is D_{2} , then \Delta_{01}=1 and \Delta_{02}=\Delta_{12}=3 , so \Delta=3 . But are there perhaps other quantities describing how complex the arrangement \mathcal{A} can be, yet be bounded in terms of n and \Delta ? The first quantity we will study is the diameter of the dual graph of the arrangement. The dual graph of the arrangement \mathcal{A} is the graph \mathcal{G}^{*}:=\mathcal{G}^{*}(\mathcal{A}) whose nodes correspond to the faces in \mathcal{A} and two nodes in \mathcal{G}^{*} are adjacent if and only if the corresponding faces have at least one edge in common; see Fig. 1 (ii). The diameter of \mathcal{G}^{*} is the maximum hop-distance between any two nodes in \mathcal{G}^{*} . The second quantity of interest is the number of maximal faces in \mathcal{A} . Let ply of a face in \mathcal{A} be the number of disks in \mathcal{D} that contain the face. Two faces are called neighbors in \mathcal{A} if they have at least one common edge, i.e., if their corresponding nodes in \mathcal{G}^{*} are adjacent. A face is called maximal if its ply is larger than the ply of