Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

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 NPhard. Furthermore, we show that the problem is kLDThard. 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.more » « less

Dujmovic and Langerman (2013) proved a hamsandwich cut theorem for an arrangement of lines in the plane. Recently, Xue and Soberon (2019) generalized it to balanced convex partitions of lines in the plane. In this paper, we study the computational problems of computing a hamsandwich cut balanced convex partitions for an arrangement of lines in the plane. We show that both problems can be solved in polynomial time.more » « less

Let P be a set n points in a ddimensional 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).more » « less

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). Generalized 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 ofktranspositions. 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 optimizing allowable sequences. Using this approach, we find new bounds forhalving pseudolines for evenn,n≤100.more » « less