# Accession Number:

## ADA413624

# Title:

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

# Descriptive Note:

## Conference paper

# Corporate Author:

## DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1997-01-01

# Pagination or Media Count:

## 9.0

# 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 On 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, On2k23, on the complexity of the k-th level in an arrangement of n planes in the set of real numbers3, 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 On32, and that the complexity of any single level in an arrangement of n triangles in 3-space is On176.

# Subject Categories:

- Theoretical Mathematics