论文标题
改进了Tverberg分区的近似算法
Improved Approximation Algorithms for Tverberg Partitions
论文作者
论文摘要
$ \ newCommand {\ flo} [1] {\ left \ lfloor {＃1} \ right \ rfloor} \ renewcommand {\ re} {\ re} {\ mathbb {r}} $ Tverberg的定理指出，$ \ re^d $中的一组$ n $点可以分为$ \ floor {n/（d+1）} $设置，并带有共同的交叉点。该交叉点（又称特维尔伯格点）的一个点是输入点集的中心点，而Tverberg分区提供了一个紧凑的证明，这在算法上有用。 不幸的是，计算tverberg点的确切需要$ n^{o（d^2）} $时间。我们为此问题提供了几种新的近似算法，这些算法可以改善近似的运行时间或质量，或两者兼而有之。特别是，我们提供了第一个强烈的多项式（在$ n $和$ d $中），用于查找Tverberg点。
$\newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor} \renewcommand{\Re}{\mathbb{R}}$ Tverberg's theorem states that a set of $n$ points in $\Re^d$ can be partitioned into $\floor{n/(d+1)}$ sets with a common intersection. A point in this intersection (aka Tverberg point) is a centerpoint of the input point set, and the Tverberg partition provides a compact proof of this, which is algorithmically useful. Unfortunately, computing a Tverberg point exactly requires $n^{O(d^2)}$ time. We provide several new approximation algorithms for this problem, which improve either the running time or quality of approximation, or both. In particular, we provide the first strongly polynomial (in both $n$ and $d$) approximation algorithm for finding a Tverberg point.
