On the Average Complexity of the k-Level

2019/11/06 by Chiu, Man-Kwun, Felsner, Stefan, Scheucher, Manfred +3
#52C30 #68Q25 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #I.3.5

paper · doi:10.48550/arxiv.1911.02408

Abstract

Let \cal L be an arrangement of n lines in the Euclidean plane. The k-level of \cal L consists of all 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⋅ (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, the south pole. We prove an upper bound of O((k+1)²) 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 \mathbbS^d which are orthogonal to a set of random points on \mathbbS^d. In this model, we prove that the expected complexity of the k-level is of order Θ((k+1)^d-1).

Related

• The Maximum-Level Vertex in an Arrangement of Lines
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• The information content of points on lines and k-plane extensions
• On the zone of a circle in an arrangement of lines
• Better Late than Never: the Complexity of Arrangements of Polyhedra