%ABereg Sergey, Haghpanah%D2020%I
%K
%MOSTI ID: 10196125
%PMedium: X
%TAlgorithms for Radon Partitions with Tolerance
%XLet P be a set n points in a d-dimensional space. Tverberg
theorem says that, if n is at least (k − 1)(d + 1), then P can be par-
titioned into k sets whose convex hulls intersect. Partitions with this
property are called Tverberg partitions. A partition has tolerance t if
the partition remains a Tverberg partition after removal of any set of t
points from P. A tolerant Tverberg partition exists in any dimensions
provided that n is sufficiently large. Let N(d,k,t) be the smallest value
of n such that tolerant Tverberg partitions exist for any set of n points
in R d . Only few exact values of N(d,k,t) are known.
In this paper, we study the problem of finding Radon partitions (Tver-
berg partitions for k = 2) for a given set of points. We develop several
algorithms and found new lower bounds for N(d,2,t).