No-Dimensional Tverberg Theorems and Algorithms.

Area of Science:

• Computational Geometry
• Combinatorial Geometry

Background:

• Tverberg's theorem guarantees partitioning points into k subsets with intersecting convex hulls.
• The computational complexity of finding such partitions remains an open problem.
• Existing theorems have limitations regarding point set size and exact intersection requirements.

Purpose of the Study:

• To present a deterministic algorithm for an approximate Tverberg partitioning problem.
• To provide an efficient and simple notion of approximation for Tverberg's theorem.
• To generalize Sarkaria's method for algorithmic applications.

Main Methods:

• Generalizing Sarkaria's method to reduce Tverberg's problem to the colorful Carathéodory problem.
• Applying the reduction algorithmically to geometric partitioning problems.
• Developing a deterministic algorithm with a time complexity of O(n^d).

Main Results:

• A deterministic algorithm finds a k-partition of n points in O(n^d) time.
• The algorithm guarantees that a ball of radius 1/k intersects each subset's convex hull.
• This provides an efficient approximate solution to the Tverberg partitioning problem.

Conclusions:

• The study offers an efficient algorithmic approach to approximate Tverberg partitioning.
• The generalized Sarkaria's method proves effective for both no-dimensional and colorful Tverberg problems.
• The findings introduce a novel and practical approximation strategy in computational geometry.