TY - GEN

T1 - A theorem of bárány revisited and extended

AU - Mustafa, Nabil H.

AU - Ray, Saurabh

PY - 2012

Y1 - 2012

N2 - The colorful Carathéodory theorem [Bár82] states that given d+1 sets of points in ℝ d, the convex hull of each containing the origin, there exists a simplex (called a 'rainbow simplex') with at most one point from each point set, which also contains the origin. Equivalently, either there is a hyperplane separating one of these d + 1 sets of points from the origin, or there exists a rainbow simplex containing the origin. One of our results is the following extension of the colorful Carathéodory theorem: given ⌊d/2⌋ + 1 sets of points in ℝ d, and a convex object C, then either one set can be separated from C by a constant (depending only on d) number of hyperplanes, or there is a ⌊d/2⌋-dimensional rainbow simplex intersecting C.

AB - The colorful Carathéodory theorem [Bár82] states that given d+1 sets of points in ℝ d, the convex hull of each containing the origin, there exists a simplex (called a 'rainbow simplex') with at most one point from each point set, which also contains the origin. Equivalently, either there is a hyperplane separating one of these d + 1 sets of points from the origin, or there exists a rainbow simplex containing the origin. One of our results is the following extension of the colorful Carathéodory theorem: given ⌊d/2⌋ + 1 sets of points in ℝ d, and a convex object C, then either one set can be separated from C by a constant (depending only on d) number of hyperplanes, or there is a ⌊d/2⌋-dimensional rainbow simplex intersecting C.

KW - Caratheodory's theorem

KW - Colorful caratheodory theorem

KW - Discrete geometry

KW - Hadwiger-debrunner (p

KW - Q)-theorem

KW - Weak e-nets

UR - http://www.scopus.com/inward/record.url?scp=84863891780&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863891780&partnerID=8YFLogxK

U2 - 10.1145/2261250.2261300

DO - 10.1145/2261250.2261300

M3 - Conference contribution

AN - SCOPUS:84863891780

SN - 9781450312998

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 333

EP - 337

BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012

T2 - 28th Annual Symposuim on Computational Geometry, SCG 2012

Y2 - 17 June 2012 through 20 June 2012

ER -