## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, March 16, 2004, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Uli Wagner (Charles University, Prague)

## On Halving Simplices in 4 Dimensions (Part I)

This will be a miniseries of two talks on the subject of $k$-sets and $k$-facets. The goal is twofold: On the one hand, to give a brief overview of and introduction to the problem, and on the other hand to describe recent progress in four dimensions.

The basic definition is as follows. Let $S$ be a set of $n$ points in general position in $\R^d$, with $n-d$ even. A halving simplex of $S$ is a $(d-1)$-dimensional simplex $\sigma$ (a segment in the plane, a triangle in three dimensions, etc.), spanned by $d$ points of $S$, such that the hyperplane $h$ spanned by $\sigma$ halves the remaining points, i.e., there are exactly $(n-d)/2$ points of $S$ on either side of $h$.

More generally, if there are $k$ points on one side of $h$ and $n-d-k$ on the other, then the simplex $\sigma$ is called a $k$-facet of $S$. These objects appear in many contexts in discrete and computational geometry (such as randomized incremental convex hull algorithms, range searching, or rectilinear crossing numbers, to name but a few), and the fundamental combinatorial question is: What is the maximum number of $k$-facets of any $n$-point set in dimension $d$? As usual in computational geometry, the dimension $d$ is considered fixed, and we are interested in the asymptotic behaviour as $n$ and $k$ tend to infinity. It turns out that the special case of halving facets is really the crucial one, as bounds for them yield bounds for all other values of $k$ as well.

In the first part, on Tuesday, we will give a brief overview of the problem and of the current state of knowledge. The focus will be on the general methods used to prove the upper bounds, which are of the order $n^{d-cd}$ with some constant 0 < cd < 1 depending on $d$. (The best lower bounds are only slightly larger than $n^{d-1}$). The problem is unsolved even in the plane (where the upper bound is $n^{4/3}$), but the situation gets rapidly worse as the dimension grows: The known proofs only yield a constant $cd$ that tends to zero exponentially fast as $d$ grows.

Next, we will then formulate two new lemmas which yield an improved bound of rougly $n^{4-2/45}$ in four dimensions. As we see it, the interesting point here is not so much the concrete numerical improvement over previous bounds (which, as such, might not seem so terribly exciting), but the new method, an extension of the so-called Lovasz Lemma to planes, and the fact that it is proved by elementary methods (as opposed to topological ones, on which the previous bounds in higher dimensions relied).

In the second part, on Thursday, we will discuss the two lemmas, their proofs, and possible extensions, in more detail.

(Joint work with Jiri Matousek and Micha Sharir)

Information for students and suggested topics for student talks