On levels in arrangements of lines, segments, planes, and triangles
Pankaj K. Agarwal, Boris S. Aronov, Micha Sharir · 1997
We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem.(a) We review sad simplifi some old proofs in new dwguise and give new proofs of the bound O(n~) for the complexity of the k-th level in an arrangement of n lines.(b) We derive an improved version of Lcn%az Lemma in any dimension, and use it to prove a new bound, 0(n2k2/3), on the complexity of the k-th level in an mangement of n planes in lR3, or on the number of k-sets in a set of n points in three dimensions.(c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n312 ), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17'6 ).