In the well-known "k-set" problem (first considered by Lovasz, Erdos, and others in the 1970s, and later studied extensively by many computational geometers), we wish to bound the maximum number of subsets of size exactly k that can be formed by intersecting an n-point set with a halfspace. The problem in two dimensions is equivalent to determining the combinatorial complexity of the k-level in an arrangement of lines. In this talk, I will survey some recent approaches to proving nontrivial upper bounds for this problem and its generalizations to k-levels of curves and surfaces. Many open questions will be mentioned.
Copyright. All Rights Reserved.