Let {\cal A } be an arrangement of n lines in the Euclidean plane. The <i>k-level<i> of {\cal A } consists of all intersection points v of lines in%DIFDELCMD < {\cal %%% A which have exactly k lines of {\cal 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\cdot (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 cellto 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 (\leq j)-zone in a d-dimensional simple arrangement of n hyperplanes is of order \Theta((j+1)n^{d-1 We also consider arrangements of great (d-1)-spheres on the sphere \mathbb{S}^d which are orthogonal to a set of random points on \mathbb{S}^d. In this model  we prove that the expected complexity of the k-level is of order \Theta((k+1)^{d-1}).
Let {\cal L } be an arrangement of n lines in the Euclidean plane. The k-level of {\cal L } consists of all %DIFDELCMD < {\cal %%% vertices v of the arrangement which have exactly k lines of {\cal 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\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 at most k to a marked cell, thesouth 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 sphere \mathbb{S}^d which are orthogonal to a set of random points on \mathbb{S}^d. In this model , we prove that the expected complexity of the k-level is of order \Theta((k+1)^{d-1}).
R
A
L
R
<i>k-level<i>
k-level
R
A
L
D
intersection points v of lines in
R
A
vertices v of the arrangement
R
A
L
A
(the maximum size)
R
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 cellto contain the south-pole, we
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 at most k to a marked cell, the
A
south pole
A
. We
R
. As a byproduct we show that the complexity of any (\leq j)-zone in a d-dimensional simple arrangement of n hyperplanes is of order \Theta((j+1)n^{d-1
in great-circle arrangements if the south pole is chosen uniformly at random among all cells.
A
,