A Theorem of Baranv Revisited and Extended

摘要

The colorful Caratheodory theorem [Bar82] states that given d + 1 sets of points in R~d, the convex hull of each containing the origin, there exists a simplex (called a 'rainbow simplex') with at most one point from each point set, which also contains the origin. Equiv-alently, either there is a hyperplane separating one of these d + 1 sets of points from the origin, or there exists a rainbow simplex containing the origin. One of our results is the following extension of the colorful Caratheodory theorem: given [d/2 + 1 sets of points in R~d, and a convex object C, then either one set can be separated from C by a constant (depending only on d) number of hyperplanes, or there is a [d/2]-dimensional rainbow simplex intersecting C.