Search for: All records

Let 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). 

LetPbe a set of points in general position in the plane. Ahalving lineofPis a line passing through two points ofPand cuttingthe remainingn−2 points in a half (almost half ifnis odd). Gener-alized configurations of points and their representations using allowablesequences are useful for bounding the number of halving lines.We study a problem of finding generalized configurations of pointsmaximizing the number of halving pseudolines. We develop algorithmsfor optimizing generalized configurations of points using the new notionofpartial allowable sequenceand the problem of computing a partialallowable sequence maximizing the number ofk-transpositions. It canbe viewed as a sorting problem using transpositions of adjacent elementsand maximizing the number of transpositions at positionk.We show that this problem can be solved inO(nkn) time for anyk>2, and inO(nk)timefork=1,2. We develop an approach for opti-mizing allowable sequences. Using this approach, we find new bounds forhalving pseudolines for evenn,n≤100.