UC Davis

A halving line of a set of points is a line that divides the set of points into two equal parts. The halving lines problem asks: What is the maximum number of distinct halving lines that a set of n points can have? The focus of this dissertation is on results either about or inspired by the halving lines problem and its variations and generalizations. We start out by generalizing the halving lines problem in the most natural way: Given a family of curves or surfaces and a set of points, we want to know how many ways there are to divide the set of points into two equal parts using one of the curves or surfaces in the given family. And we would also like to know what the maximum number of halving curves or surfaces that a set of n points can have is. This type of problem leads us to ask several new questions which are relevant to discrete geometry, convex geometry, as well as real algebraic geometry. Some of our main contributions are as follows:

We study a variation on the halving lines problem when the family of separating curves or surfaces is a parametric family of algebraic curves or surfaces. In some cases, we are able to exactly count the number of halving curves. An example when we obtain an exact count is for the conic sections. These results are similar to a result of Ardila on halving circles.

The concept of neighborliness is crucial for several of our results. Neighborly polytopes are important to the theory of convex polytopes because of their appearance in the upper bound theorem of McMullen. The moment curve is the standard way to construct neighborly polytopes. We define generally neighborly manifolds and algebraic varieties. These objects can be seen as higher-dimensional analogues of the moment curve.

We study the random version of the original k-set problem in the plane and establish an improved upper bound for the expected number of k-sets. We also investigate how it may be possible to improve our bound using the continuous version of the polynomial partitioning theorem of Guth and Katz. This motivates a question about the points of intersection of an algebraic curve and the k-edge graph of a set of points.

Another variation on the random version of the k-set problem is introduced and essentially solved: We obtain nearly tight bounds for the expected number of ways one can enclose k points from a random set of points using a translation of a fixed strictly convex body in the plane. The motivation is to show that a technique for counting k-sets due to Barany and Steiger is nearly tight for a natural variation on the k-set problem.

A theme throughout this work is the investigation of questions whose answers help us understand the limits of an argument or proof technique. Most of the ideas presented here also appeared in papers coauthored with Luis Rademacher.