On Levels in Arrangements of Lines, Segments, Planes, and Triangles
Abstract
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 and simplify some old proofs in new disguise and give new proofs of the bound O(n the square root of k + 1) for the complexity of the k-th level in an arrangement of n lines. (b) We derive an improved version of Lovasz Lemma in any dimension, and use it to prove a new bound, O(n2k2/3), on the complexity of the k-th level in an arrangement of n planes in the set of real numbers(3), 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(n3/2), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17/6).
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1997
- Accession Number
- ADA413624
Entities
People
- Boris Aronov
- Micha Sharir
- Pankaj Agarwal
Organizations
- Duke University