Improved Approximation Algorithms for Tverberg Partitions
$
\newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r}
\newcommand{\Mh}[1]{#1}
\newcommand{\query}{q}
\newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\pt}{p}
\newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|}
\newcommand{\ptq}{q}
\newcommand{\pts}{s}$
Sariel Har-Peled,
and
Timothy Zhou.
Tverberg's theorem states that a set of $n$ points in $\Re^d$ can
be partitioned into $\ceil{n/(d+1)}$ sets whose convex hulls all
intersect. A point in the intersection (aka Tverberg point) is a
centerpoint, or high-dimensional median, of the input point set.
While randomized algorithms exist to find centerpoints with some
failure probability, a partition for a Tverberg point provides a
certificate of its correctness.
Unfortunately, known algorithms for computing exact Tverberg
points take $n^{O(d^2)}$ time. We provide several new
approximation algorithms for this problem, which improve running
time or approximation quality over previous work. In particular,
we provide the first strongly polynomial (in both $n$ and $d$)
approximation algorithm for finding a Tverberg point.
PDF.
:
arXiv.
Last modified: Sat 2022-07-23 20:03:36 UTC 2022 by Sariel Har-Peled