An optimal generalization of the Colorful Carathéodory theorem

The Colorful Caratheodory theorem by Barany (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 Caratheodory 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 .

• Publication year

  2016

• Venue

  Discrete Mathematics

• Publication date

  2016-04-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.disc.2015.11.019
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A note on order-type homogeneous point sets

  2013influential reference
• Centerpoints and Tverberg's technique

  2010cited by this paper
• An optimal extension of the centerpoint theorem

  2009cited by this paper
• Weak epsilon-nets have basis of size O(1/epsilonlog(1/epsilon)) in any dimension

  2008cited by this paper
• On Center Regions and Balls Containing Many Points

  2008cited by this paper
• Combinatorial Geometry

  2006cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Piercing and Selection Theorems in Convexity (lecture Notes)

  1999cited by this paper
• Improved bounds on weak ε-nets for convex sets

  1993cited by this paper
• Almost tight bounds forɛ-Nets

  1992cited by this paper
• Piercing convex sets and the hadwiger-debrunner (p

  1992cited by this paper
• Circles through two points that always enclose many points

  1989cited by this paper
• Applications of random sampling in computational geometry, II

  1988cited by this paper
• ɛ-nets and simplex range queries

  1987cited by this paper
• Epsilon-nets and simplex range queries

  1986cited by this paper
• A generalization of carathéodory's theorem

  1982influential reference
• A Theorem on General Measure

  1946cited by this paper
• Combinatorics, Probability and Computing Point Selections and Weak Ε-nets for Convex Hulls Point Selections and Weak E-nets for Convex Hulls

  year unknowncited by this paper

• On covering dimension and sections of vector bundles

  2023influential citation
• Theorems of Carathéodory, Helly, and Tverberg Without Dimension

  2018cites this paper
• On a Problem of Danzer

  2018cites this paper
• 2 01 7 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2017cites this paper
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

  2017influential citation
• Epsilon-Approximations & Epsilon-Nets

  2017cites this paper
• Fe b 20 17 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2017cites this paper
• 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2016cites this paper