An optimal generalization of the Colorful Carathéodory theorem

Nabil H. Mustafa, Saurabh Ray

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1300-1305
Number of pages6
JournalDiscrete Mathematics
Volume339
Issue number4
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'An optimal generalization of the Colorful Carathéodory theorem'. Together they form a unique fingerprint.

Cite this