On the average complexity of the $k$-level

• Main Authors: Chiu, Man-Kwun, Felsner, Stefan, Scheucher, Manfred, Schnider, Patrick, Steiner, Raphael, Valtr, Pavel
• Format: Text
• Language: English
• Published: Journal of Computational Geometry 2020
• Subjects: South Pole; South pole
• Online Access: https://dx.doi.org/10.20382/jocg.v11i1a19; https://jocg.org/index.php/jocg/article/view/3109

$\newcommand{\LL}{\mathcal{L}}\newcommand{\SS}{\mathcal{S}}$Let \(\LL\) be an arrangement of \(n\) lines in the Euclidean plane. The \(k\)-level of \(\LL\) consists of all vertices \(v\) of the arrangement which have exactly \(k\) lines of \(\LL\) passing below \(v\). The complexity (the maximum size) of the \(k\)-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of \(O(n\cdot (k+1)^{1/3})\). Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the \(k\)-level denotes the vertices at distance \(k\) to a marked cell, the south pole. We prove an upper bound of \(O((k+1)^2)\) on the expected complexity of the \((\le k)\)-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great \((d-1)\)-spheres on the \(d\)-sphere \(\SS^d\) which are orthogonal to a set of random points on \(\SS^d\). In this model, we prove that the expected complexity of the \(k\)-level is of order \(\Theta((k+1)^{d-1})\). In both scenarios, our bounds are independent of $n$, showing that the distribution of arrangements under our sampling methods differs significantly from other methods studied in the literature, where the bounds do depend on $n$. : Journal of Computational Geometry, Vol. 11 No. 1 (2020)