A theorem of bárány revisited and extended

Nabil H. Mustafa; Saurabh Ray

doi:10.1145/2261250.2261300

A theorem of bárány revisited and extended

Nabil H. Mustafa, Saurabh Ray

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Pages	333-337
Number of pages	5
DOIs	https://doi.org/10.1145/2261250.2261300
State	Published - 2012
Event	28th Annual Symposuim on Computational Geometry, SCG 2012 - Chapel Hill, NC, United States Duration: Jun 17 2012 → Jun 20 2012

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	28th Annual Symposuim on Computational Geometry, SCG 2012
Country/Territory	United States
City	Chapel Hill, NC
Period	6/17/12 → 6/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

Access to Document

10.1145/2261250.2261300

Cite this

@inproceedings{3c9ff00b599343d59f8211e000488bff,

title = "A theorem of b{\'a}r{\'a}ny revisited and extended",

abstract = "The colorful Carath{\'e}odory theorem [B{\'a}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{\'e}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.",

keywords = "Caratheodory's theorem, Colorful caratheodory theorem, Discrete geometry, Hadwiger-debrunner (p, Q)-theorem, Weak e-nets",

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

year = "2012",

doi = "10.1145/2261250.2261300",

language = "English (US)",

isbn = "9781450312998",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "333--337",

booktitle = "Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012",

note = "28th Annual Symposuim on Computational Geometry, SCG 2012 ; Conference date: 17-06-2012 Through 20-06-2012",

}

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 -

A theorem of bárány revisited and extended

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this