On the average complexity of the k-level

Abstract

Let L be an arrangement of n lines in the Euclidean plane. The k-level of L consists of all vertices v of the arrangement which have exactly k lines of L 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.(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 (<= 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 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 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.