The celebrated Carathéodory’s theorem states that any 0-embracing set in R^d has a 0-embracing subset of size at most d+1, where a set of points is 0-embracing if the origin is contained in its convex hull.  Imre Bárány discovered a colorful extension to this theorem in 1982, demonstrating that for any family of d+1 0-embracing sets, there exists a 0-embracing simplex containing one point from each. The sets can be considered as color classes, making the final solution colorful. The problem has several interesting connections to other geometric problems. For instance, finding a center point and a Tverberg partition can be reduced to instances of colorful Carathéodory.

 

Bárány’s theorem is proved by a pivoting algorithm that produces a sequence of 0-embracing colorful simplices that creep closer to containing the origin. Like the Simplex Algorithm, the algorithm has no known poly-time implementation. Indeed, devising any poly-time algorithm that outputs a 0-embracing colorful simplex is a fundamental open question in computational complexity. We review several variations which have been studied including the 2-color case for which we provide a new (arguably simpler) algorithm based on parametric paths. We then introduce a generalization of this which admits a very different type of algorithm.

 

This is joint work with Kamyar Khodamoradi, Joseph Paat, and Bruce Shepherd.