Algorithmic aspects of Tverberg's Theorem

David Rolnick, Pablo Soberón

Abstract

Tverberg's Theorem is a cornerstone of combinatorial geometry, asserting that any sufficiently large set of points in $\mathbb{R}^d$ can be partitioned into $k$ subsets whose convex hulls share a common intersection. While the existence of such partitions is guaranteed, their computation remains a challenge. This paper establishes a constructive relationship between Tverberg partitions and centerpoint approximations. We present weakly polynomial probabilistic algorithms for Euclidean spaces and integer lattices, and deterministic algorithms for specific graph structures under geodetic convexity. Conversely, we demonstrate that finding Radon partitions in general graphs is NP-hard.

Introduction

In 1966, Helge Tverberg proved that for any set $P$ of at least $(k-1)(d+1)+1$ points in $\mathbb{R}^d$, there exists a partition into $k$ disjoint subsets $P_1, \dots, P_k$ such that $\bigcap_{i=1}^k \text{conv}(P_i) \neq \emptyset$. A related concept is the Centerpoint Theorem, which guarantees a point $c$ such that every closed halfspace containing $c$ contains at least $n/(d+1)$ points of $P$.

It is well-understood that any point in the intersection of a Tverberg partition is a centerpoint. This research explores the inverse: can we leverage algorithms that find centerpoints to efficiently construct Tverberg partitions? Furthermore, the authors extend this inquiry into the realm of abstract convexity spaces, specifically geodetic convexity in graphs, where the "convex hull" of a vertex set is defined by the union of all shortest paths between them.

Algorithmic Approaches

1. Euclidean Space and Integer Lattices

The primary contribution for Euclidean space is an iterative "peeling" algorithm. The process follows three main steps:

  1. Centerpoint Approximation: Utilize existing probabilistic algorithms (such as those by Clarkson et al.) to identify an approximate centerpoint of the current point set.
  2. Subset Identification: Apply Carathéodory's theorem—implemented via linear programming—to find a minimal subset of at most $d+1$ points whose convex hull contains the identified centerpoint.
  3. Iterative Removal: This subset is designated as one part of the Tverberg partition and removed from the dataset. The process repeats until the desired number of partitions is reached.

For integer lattices, the authors generalize this approach using Doignon's theorem (the integer analog of Helly's theorem) and integer programming to ensure the intersection point of the hulls also resides on the integer lattice.

2. Geodetic Convexity in Graphs

The paper shifts from continuous geometry to discrete graph structures, focusing on geodetic convexity. The complexity of finding partitions varies significantly by graph topology:

  • Trees: The authors provide a deterministic $O(n)$ algorithm. By working inward from the leaves, the algorithm identifies a central node that effectively shatters the tree into components small enough to satisfy the partition requirements.
  • Cactus Graphs: For graphs where any two vertices are connected by at most two simple paths, the authors employ the discrete ham sandwich theorem on auxiliary graph structures to find vertex pairs that act as joint centerpoints. This yields a deterministic $O(n^2)$ algorithm.

Key Results and Complexity

Euclidean Performance

The randomized algorithm successfully identifies a $k$-Tverberg partition for $k = \lceil n / (d(d+1)^2) \rceil$. The running time is weakly polynomial in the number of points $n$, the dimension $d$, and the confidence parameter $\log(1/\epsilon)$. This is a significant result as it maintains efficiency across all variables, even if it does not yet reach the optimal Tverberg bound of $k \approx n/d$.

Hardness in General Graphs

While specific graph classes yield to efficient algorithms, the general case does not. The authors prove that the Graph-Radon problem (finding a Tverberg partition for $k=2$) is NP-hard through a polynomial-time reduction from the Boolean Satisfiability Problem (SAT). Additionally, they show that counting the number of valid Radon partitions is #P-hard.

Discussion and Future Work

This work demonstrates that centerpoint approximations are a powerful tool for constructing Tverberg partitions, bridging a gap between existence proofs and practical computation. However, several open questions remain. The Euclidean algorithms currently require a trade-off: to achieve weakly polynomial time, one must accept a partition count $k$ that is lower than the theoretical optimum ($n/d^2$ or $n/d^3$ vs. $n/d$).

In the graph-theoretic context, the jump from the efficiency of cactus graphs to the NP-hardness of general graphs suggests a rich area for future research in approximation algorithms for broader graph classes. Tightening the bounds for integer Tverberg partitions also remains a significant open problem in the field.

Summary updated

Abstract

We obtain algorithms for computing Tverberg partitions based on centerpoint approximations. This applies to a wide range of convexity spaces, from the classic Euclidean setting to geodetic convexity in graphs. In the Euclidean setting, we present probabilistic algorithms which are weakly polynomial in the number of points and the dimension. For geodetic convexity in graphs, we obtain deterministic algorithms for cactus graphs and show that the general problem of finding the Radon number is NP-hard.
BibTeX
@misc{rolnick2016algorithmic,
  author = {David Rolnick and Pablo Soberón},
  title = {{Algorithmic aspects of Tverberg's Theorem}},
  year = {2016},
  eprint = {1601.03083},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.03083},
}

Loading related content...

Figure