The Colorful Carathéodory Problem and its Descendants

Abstract

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.

Der bunte Satz von Carathéodory ist eine Existenzaussage, die verschiedene Resultate in der konvexen Geometrie nach sich zieht. Dazu gehören unter anderem der Satz von Tverberg, die Existenz von Zentrumspunkten, das erste Selektionslemma und der bunte Satz von Kirchberger. Diese Beweise können als Polynomialzeitreduktionen auf CCP, das zu dem bunten Satz von Carathéodory gehörende algorithmische Problem, interpretiert werden. In dieser Arbeit werden Approximationsalgorithmen und Komplexitätsschranken entwickelt, die aufgrund der Polynomialzeitreduktionen auf CCP auch auf die oben genannten Probleme übertragbar sind. Seien C_1,...,C_(d+1) \subset R^d endliche Punktmengen, sodass der Ursprung in der konvexen Hülle jeder Punktmenge C_i, i \in [d+1], enthalten ist. Der bunte Satz von Carathéodory garantiert nun die Existenz einer Auswahl c_1 \in C_1, ..., c_(d+1) \in C_(d+1), welche den Ursprung ebenfalls in der konvexen Hülle enthält. CCP beschreibt dann das Problem, diese Auswahl zu berechnen. Da immer eine Lösung existiert und eine Kandidatenlösung in Polynomialzeit überprüfbar ist, liegt CCP in der Komplexitätsklasse totale Funktionen NP (TFNP), die Klasse der NP-Suchprobleme für die immer eine Lösung existiert. In dieser Arbeit wird gezeigt, dass CCP im Schnitt zweier wichtiger Unterklassen von TFNP enthalten ist: der Komplexitätsklasse Polynomialzeitparitätsargument in gerichteten Graphen (PPAD) und in der Komplexitätsklasse polynomielle lokale Suche (PLS). Die Formulierung von CCP als PPAD-Problem basiert auf einem neuen konstruktiven Beweis des bunten Satzes von Carathéodory durch Sperners Lemma. Des Weiteren wird gezeigt, dass schon eine kleine Änderung in der Definition von CCP zu einem PLS-vollständigen Problem führt. Im zweiten Teil der Arbeit werden verschiedene konstruktive Resultate vorgestellt. Zuerst wird das Approximationsproblem betrachtet, indem mehr als ein Punkt von jeder Menge C_i ausgewählt werden kann. Dies ist mit den Polynomialzeitreduktionen auf CCP kompatibel. Es wird gezeigt, dass für jedes feste eps > 0 eine Auswahl C mit maximal \lceil eps d\rceil Punkten von jeder Menge C_i in Polynomialzeit gefunden werden kann, sodass 0 \in conv(C). Zusätzlich wird ein verwandtes Approximationsproblem betrachtet, in dem die Eingabe aus k < d+1 Mengen C_i besteht mit 0 \in conv(C_i) für i \in [k] und eine Auswahl C mit 0 \in conv(C) gefunden werden soll, die maximal \lceil (d+1) / k \rceil Punkte von jeder Menge C_i enthält. Die Existenz von C ist eine direkte Implikation des bunten Satzes von Carathéodory. Mithilfe von linearen Programmen ist es möglich, dieses Problem für den Fall k=2 in schwach polynomieller Zeit zu lösen. Des Weiteren wird gezeigt, dass CCP exakt in quasi-polynomieller Zeit gelöst werden kann, falls die Eingabe aus poly(d) Mengen besteht, anstatt nur aus d+1. Abschließend wird das Problem der simplizialen Tiefe betrachtet. Die simpliziale Tiefe sigma_P(q) eines Punktes q \in R^d bezüglich einer Menge P \subset R^d ist die Anzahl aller verschiedener d-Simplexe mit Ecken in P, die q enthalten. Es wird gezeigt, dass sigma_P(q) in ~O(n^(d/2+1)) Zeit mit hoher Wahrscheinlichkeit (1+eps)-approximiert werden kann für eps > 0 fest. Für den Fall, dass die Dimension Teil der Eingabe ist, wird bewiesen, dass das Problem #P-vollständig und W[1]-schwer ist.