Let A be an arrangement of n lines in the Euclidean plane. The k-level of A consists of all intersection points v of lines in A which have exactly k lines of A passing below v. The complexity of the k-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of O(n · (k + 1) 1/3 ). We investigate the complexity of k-levels in random line and hyperplane arrangements. When the arrangement is obtained from any fixed projective line arrangement of n lines by choosing a random cell to contain the south-pole, we prove an upper bound of O((k + 1) 2 ) on the expected complexity of the k-level. As a byproduct we show that the complexity of any (≤ j)-zone in a d-dimensional simple arrangement of n hyperplanes is of order Θ((j + 1)n d−1 ). The classical zone theorem is the case j = 0. We also consider arrangements of great (d − 1)-spheres on the sphere S d which are orthogonal to a set of random points on S d . In this model we prove that the expected complexity of the k-level is of order Θ((k + 1) d−1 ).
The recent work of Chiu et al. REF comes closer, as they have looked at the average size of the jth level in a random planar arrangement of n lines, chosen by fixing a projective line arrangement of size n and equiprobably choosing a random cell to contain the south-pole.
On the Average Complexity of the $k$-Level
ArXiv
ArXiv
Mathematics Computer Science