Search for: All records

Caratheodory’s theorem says that any point in the convex hull of a set $P$ in $R^d$ is in the convex hull of a subset $P'$ of $P$ such that $|P'| \le d + 1$. For some sets P, the upper bound d + 1 can be improved. The best upper bound for P is known as the Caratheodory number [2, 15, 17]. In this paper, we study a computational problem of finding the smallest set $P'$ for a given set $P$ and a point $p$. We call the size of this set $P'$, the Caratheodory number of a point p or CNP. We show that the problem of deciding the Caratheodory number of a point is NP-hard. Furthermore, we show that the problem is k-LDT-hard. We present two algorithms for computing a smallest set $P'$, if CNP= 2,3. Bárány [1] generalized Caratheodory’s theorem by using d+1 sets (colored sets) such that their convex hulls intersect. We introduce a Colorful Caratheodory number of a point or CCNP which can be smaller than d+1. Then we extend our results for CNP to CCNP. 

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.