A theorem of bárány revisited and extended

Nabil H. Mustafa, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Pages333-337
Number of pages5
DOIs
StatePublished - 2012
Event28th Annual Symposuim on Computational Geometry, SCG 2012 - Chapel Hill, NC, United States
Duration: Jun 17 2012Jun 20 2012

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other28th Annual Symposuim on Computational Geometry, SCG 2012
CountryUnited States
CityChapel Hill, NC
Period6/17/126/20/12

Keywords

  • Caratheodory's theorem
  • Colorful caratheodory theorem
  • Discrete geometry
  • Hadwiger-debrunner (p
  • Q)-theorem
  • Weak e-nets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A theorem of bárány revisited and extended'. Together they form a unique fingerprint.

Cite this