Abstract:

Helly's theorem says that if every $d+1$ elements of a given finite
set of convex objects in $\RR^d$ have a common point, then there is a
point common to all of the objects in the set.

We define three new types of Helly theorems: discrete Helly theorems
- where the common point should belong to an a-priori given set,
lexicographic Helly theorems - where the common point should not be
lexicographically greater than a given point, and
lexicographic-discrete Helly theorems. We show the relations between
these new Helly theorems and their corresponding (standard) Helly
theorems. We obtain several new discrete and lexicographic Helly
numbers.  Using these new types of Helly theorems we get linear time
solutions for various optimization problems, mainly in the fields of
location theory and computational geometry. For this, we define a new
framework, {\em DLP-type} (Discrete Linear Programming type), and
provide new algorithms that solve in randomized linear time
fixed-dimensional DLP-type problems.

An example of a discrete Helly theorem and its corresponding discrete
optimization problem is this: Let $D$ be a set of unit intervals on
the real line, and $S$ be a set of points. If every set of $p+1$
intervals from $D$ can be pierced by $p$ points from $S$, then the
entire set $D$ of intervals can be pierced by $p$ points from $S$.
The corresponding optimization problem is just the $p$-center problem
for the midpoints of the intervals in $D$, where the centers are
restricted to be from $S$.

The talk is based upon a paper which appeared in FOCS 2004.