ON LEVELS IN ARRANGEMENTS OF LINES, SEGMENTS, PLANES, AND TRIANGLES

We consider the problem of bounding the complexity of the kth level in an arrangement of n curves or surfaces, a problem dual to, and an ext ension of, the well-known k-set problem, Among other results, we prove a new bound, O(nk(5/3)), on the complexity of the kth level in an arr angement of n planes in R-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 kth level in an arrangement of n line segments in the plane is O (n root k alpha(n/k)), and that the complexity of the kth level in an arrangem ent of n triangles in 3-space is O(n(2)k(5/6)alpha(n/k)).