An optimal generalization of the Colorful Carathéodory theorem

详细信息    查看全文

• 作者：Nabil H. Mustafa^a ; ^{mustafan@esiee.fr" class="auth_mail" title="E-mail the corresponding author} ; Saurabh Ray^b ; ^{saurabh.ray@nyu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Carath&eacute ; odory&rsquo ; s theorem ; Convexity ; Hadwiger&ndash ; Debrunner (p ; qp ; q) theorem and weak epsilon-nets ; Separating hyperplanes ; Colorful Carath&eacute ; odory&rsquo ; s theorem
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1300-1305
• 全文大小：402 K

文摘

The Colorful Carathéodory theorem by Bárány (1982) states that given d+1$d+1$ sets of points in R^d${\mathbb{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$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$\lfloor d/2\rfloor +1$ sets of points in R^d${\mathbb{R}}^d$ and a convex object C$C$, then either one set can be separated from C$C$ by a constant   (depending only on d$d$) number of hyperplanes, or there is a ⌊d/2⌋$\lfloor d/2\rfloor$-dimensional rainbow simplex intersecting C$C$.