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.
Introduction
In 1966, Helge Tverberg proved a fundamental result in discrete geometry: any sufficiently large set of points in $d$-dimensional space can be partitioned into $k$ subsets such that the convex hulls of all those subsets intersect at a common point. While the existence of such a partition is guaranteed when the number of points $n \ge (k-1)(d+1) + 1$, finding this partition computationally has historically been a "nightmare" for high-dimensional data. Previous approaches often suffered from superpolynomial runtimes as dimensions increased or required the number of partitions to be significantly smaller than the theoretical limit.
This paper bridges the gap between theoretical existence and computational efficiency by leveraging the concept of centerpoints—points located "deep" within a point set—to guide the construction of Tverberg partitions.
The Centerpoint Connection
The core innovation of this work is a reduction strategy: to find a Tverberg partition, one should first find a centerpoint. A centerpoint $z$ is a point such that every half-space containing $z$ also contains a significant fraction of the total points. While it was previously known that the intersection point of a Tverberg partition is a centerpoint, the authors invert this logic, using the centerpoint as a robust "hint" to build the partition.
The Iterative Euclidean Algorithm
In the Euclidean setting, the authors propose an iterative method:
- Approximate Centerpoint Discovery: Using probabilistic sampling techniques (specifically $\lambda$-samples), the algorithm identifies an approximate centerpoint $z$ efficiently.
- Carathéodory’s Theorem Application: This theorem states that if a point lies within the convex hull of a large set, it must also lie within the convex hull of a subset of at most $d+1$ points.
- Iterative Extraction: The algorithm identifies a small subset whose hull contains $z$, sets it aside as one part of the $k$-partition, and repeats the process with the remaining points.
This approach yields the first algorithm for Tverberg partitions that is weakly polynomial in both the number of points ($n$) and the dimension ($d$). Specifically, Theorem 1.1 provides a $k$-Tverberg partition (for $k \approx n/d^3$) in time proportional to $n, d,$ and $\log(1/\epsilon)$, where $\epsilon$ is the error probability.
Convexity in Graphs
The paper extends these concepts to "geodetic convexity" in graphs, where the convex hull of a set of nodes is defined by the vertices lying on all shortest paths between them. The computational landscape here shifts from linear algebra to combinatorics.
For simple graph structures, the authors provide efficient deterministic algorithms:
- Trees: Optimal partitions are found in linear time ($O(n)$).
- Cactus Graphs: (Graphs where cycles share at most one vertex) Partitions are found in quadratic time ($O(n^2)$).
However, the problem becomes significantly more difficult in general graphs. The authors prove that the "graph-Radon" problem (the $k=2$ case) is NP-hard, and its counting version is #P-hard, highlighting a sharp divide in complexity based on graph topology.
Key Results and Implications
- Weakly Polynomial Breakthrough: By accepting a slightly sub-optimal number of partitions ($k \approx n/d^3$) and a small probability of failure, the authors achieved a runtime that scales well with high-dimensional data.
- Integer Constraints: The Euclidean algorithm was successfully extended to the integer lattice. By incorporating Doignon’s Theorem (the integer version of Helly's Theorem), the authors ensure the intersection point can be constrained to integer coordinates.
- Fixed Dimension Optimization: For scenarios where the dimension is fixed, Theorem 1.2 achieves a partition closer to the theoretical limit ($k \approx n/d$) in $O(n^4 \log(1/\epsilon))$ time.
Limitations and Future Directions
Despite these advancements, several challenges remain. The current algorithms require more points than the theoretical Tverberg limit to guarantee a partition; reaching the optimal $k = \lceil n/(d+1) \rceil$ efficiently in high dimensions is still an open problem. Additionally, while the probabilistic algorithms are highly efficient, a deterministic weakly polynomial algorithm for the Euclidean setting has yet to be discovered. Finally, while the hardness of general graphs is established, the exact Radon numbers for many specific graph classes remain a subject for future research.
Summary updated