On Levels in Arrangements of Lines, Segments, Planes, and Triangles

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 an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk 5=3 ), on the complexity of the k-th level in an arrangement of n planes in IR 3 , or on the number of k-sets in a set of n points in three dimensions, and we show that the complexity of the k-th level in an arrangement of n line segments in the plane is O(n p kff(n=k)), and that the complexity of the k-th level in an arrangement of n triangles in 3-space is O(n 2 k 5=6 ff(n=k)). 1 Introduction Background. The k-set problem is one of the most challenging open problems in combinatorial geometry. The simplest variant of the problem is: Given a set S of n points in the plane in general position, and a parameter 0 k n \Gamma 2, what is the maximum possible The first, second, and fourth authors have been supported by a grant from the U.S.-Israeli B..