An optimal generalization of the Colorful Carathéodory theorem

Nabil H. Mustafa; Saurabh Ray

doi:10.1016/j.disc.2015.11.019

An optimal generalization of the Colorful Carathéodory theorem

Nabil H. Mustafa, Saurabh Ray

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

The Colorful Carathéodory theorem by Bárány (1982) states that given d+1 sets of points in R^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 R^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.

Original language	English (US)
Pages (from-to)	1300-1305
Number of pages	6
Journal	Discrete Mathematics
Volume	339
Issue number	4
DOIs	https://doi.org/10.1016/j.disc.2015.11.019
State	Published - Apr 6 2016

Keywords

Carathéodory's theorem
Colorful Carathéodory's theorem
Convexity
Hadwiger-Debrunner (p,q) theorem and weak epsilon-nets
Separating hyperplanes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2015.11.019

Cite this

@article{2e3a4a4ed5e243e8aad0a7bcf77bb11a,

title = "An optimal generalization of the Colorful Carath{\'e}odory theorem",

abstract = "The Colorful Carath{\'e}odory theorem by B{\'a}r{\'a}ny (1982) states that given d+1 sets of points in Rd, 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{\'e}odory theorem: given ⌊d/2⌋+1 sets of points in Rd 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.",

keywords = "Carath{\'e}odory's theorem, Colorful Carath{\'e}odory's theorem, Convexity, Hadwiger-Debrunner (p,q) theorem and weak epsilon-nets, Separating hyperplanes",

author = "Mustafa, {Nabil H.} and Saurabh Ray",

note = "Funding Information: The work of Nabil H. Mustafa in this paper has been supported by the grant ANR SAGA ( JCJC-14-CE25-0016-01 ). Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = apr,

day = "6",

doi = "10.1016/j.disc.2015.11.019",

language = "English (US)",

volume = "339",

pages = "1300--1305",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - An optimal generalization of the Colorful Carathéodory theorem

AU - Mustafa, Nabil H.

AU - Ray, Saurabh

PY - 2016/4/6

Y1 - 2016/4/6

N2 - The Colorful Carathéodory theorem by Bárány (1982) states that given d+1 sets of points in Rd, 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 Rd 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 by Bárány (1982) states that given d+1 sets of points in Rd, 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 Rd 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 - Carathéodory's theorem

KW - Colorful Carathéodory's theorem

KW - Convexity

KW - Hadwiger-Debrunner (p,q) theorem and weak epsilon-nets

KW - Separating hyperplanes

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

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

U2 - 10.1016/j.disc.2015.11.019

DO - 10.1016/j.disc.2015.11.019

M3 - Article

AN - SCOPUS:84949964704

SN - 0012-365X

VL - 339

SP - 1300

EP - 1305

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

ER -

An optimal generalization of the Colorful Carathéodory theorem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this