Algorithms for Radon Partitions with Tolerance

摘要

Let P be a set n points in a d-dimensiorial space. Tverberg theorem says that, if n is at least (k - 1)(d + 1), then P can be partitioned 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 (Tverberg partitions for k = 2) for a given set of points. We develop several algorithms and found new lower bounds for N(d,2,t).