The colorful Carathéodory theorem is an existence theorem that implies several statements on convex intersection patterns such as Tverberg's theorem, the centerpoint theorem, the first selection lemma, and the colorful Kirchberger theorem. Interestingly, these proofs can be interpreted as polynomial-time reductions to ColorfulCarathéodory, the computational search problem that corresponds to the colorful Carathéodory theorem. We exploit this existing web of reductions by developing approximation algorithms and complexity bounds on ColorfulCarathéodory that also apply to its polynomial-time descendants.

Let C_1, ...., C_(d+1) \subset R^d be finite point sets such that 0 \in conv(C_i) for i \in [d+1]. Then, the colorful Carathéodory theorem asserts that we can choose one point from each set C_i such that the chosen points C contain the origin in their convex hull. ColorfulCarathéodory is then the computational problem of finding C. Since a solution always exists and since it can be verified in polynomial time, ColorfulCarathéodory is contained in total function NP (TFNP), the class of NP search problems that always admit a solution. We show that ColorfulCarathéodory belongs to the intersection of two important subclasses of TFNP: the complexity classes polynomial-time parity argument on directed graphs (PPAD) and polynomial-time local search (PLS). The formulation of ColorfulCarathéodory as a PPAD-problem is based on a new constructive proof of the colorful Caratheodory theorem that uses Sperner's lemma. Moreover, we show that already a slight change in the definition of ColorfulCarathéodory results in a PLS-complete problem.

In the second part, we present several constructive results. First, we consider an approximation version of ColorfulCarathéodory in which we are allowed to take more than one point from each set C_i. This notion of approximation has not been studied before and it is compatible with the polynomial-time reductions to ColorfulCarathéodory. For any fixed eps > 0, we can compute a set C with 0 \in conv(C) and at most \lceil eps d \rceil points from each C_i in d^O(eps^(-1) log eps^(-1)) time by repeatedly combining recursively computed approximations for lower-dimensional problem instances. Additionally, we consider a further notion of approximation in which we are given only k < d+1 sets C_i with 0 \in conv(C_i), and we want to find a set C with at most \lceil (d+1) / k \rceil points from each set C_i. The existence of C is a direct implication of the colorful Carathéodory theorem. Using linear programming techniques, we can solve the case k=2 in weakly polynomial time. Moreover, we show that ColorfulCarathéodory can be solved exactly in quasi-polynomial time when given poly(d) sets C_i that contain the origin in their convex hulls instead of only d+1. Finally, we consider the problem of computing the simplicial depth. The simplicial depth sigma_P(q) of a point q \in R^d w.r.t. a set P is the number of distinct d-simplices with vertices in P that contain q. If the dimension is constant, we show that sigma_P(q) can be (1+eps)-approximated w.h.p. in time ~O(n^(d/2+1)), where eps > 0 is an arbitrary constant. Furthermore, we show that the problem becomes #P-complete and W[1]-hard if the dimension is part of the input.