An optimal generalization of the colorful Carathéodory theorem

DOI10.1016/j.disc.2015.11.019zbMath1333.52005OpenAlexW2198843684MaRDI QIDQ906475

Saurabh Ray, Nabil H. Mustafa

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2015.11.019

zbMATH Keywords

convexityseparating hyperplanesCarathéodory theoremcolorful Carathéodory theoremHadwiger-Debrunner \((p, q)\) theorem and weak epsilon-nets

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items (4)

Colorful Carathéodory, Helly and sierksma numbers of convexity spaces ⋮ On a problem of Danzer ⋮ On a Problem of Danzer ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal extension of the centerpoint theorem
• Centerpoints and Tverberg's technique
• \(\epsilon\)-nets and simplex range queries
• A generalization of Caratheodory's theorem
• Almost tight bounds for \(\epsilon\)-nets
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Circles through two points that always enclose many points
• Applications of random sampling in computational geometry. II
• Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension
• A NOTE ON ORDER‐TYPE HOMOGENEOUS POINT SETS
• On Center Regions and Balls Containing Many Points
• Point Selections and Weak ε-Nets for Convex Hulls
• Improved bounds on weak ε-nets for convex sets
• A Theorem on General Measure

This page was built for publication: An optimal generalization of the colorful Carathéodory theorem