Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

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)

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-c_{d}}$
with some constant 0 < c_{d} < 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
$c_{d}$ 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)

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login