Speaker: Wolfgang Mulzer, Freie Universitaet Berlin

Title: Approximating the Colorful Caratheodory Theorem

Abstract
--------
Given d+1 point sets P_1,...,P_(d+1) in R^d (the color classes) such 
that each set P_i contains the origin in its convex hull, the colorful 
Caratheodory theorem states that there is a colorful choice C which also 
contains the origin in its convex hull. Here, a colorful choice means a 
set containing at most one point from each color class. So far, the 
computational complexity of computing such a colorful choice is unknown.

We consider a new notion of approximation: a set C' is called a 
c-colorful choice if it contains at most c points from each color class. 
We show that for all eps > 0, an eps(d+1)-colorful choice containing the 
origin in its convex hull can be found in polynomial time.

Joint work with Yannik Stein