Discrepancy and approximations for bounded VC-dimension

DOI10.1007/BF01303517zbMath0795.05105OpenAlexW2173468371WikidataQ54309514 ScholiaQ54309514MaRDI QIDQ1316651

Lorenz Wernisch, Ermo Welzl, Ji{ří} Matoušek

Publication date: 11 September 1994

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01303517

zbMATH Keywords

discrepancycoloringcolors

Mathematics Subject Classification ID

Hypergraphs (05C65) Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Erd?s problems and related topics of discrete geometry (52C10) Discrete geometry (52C99)

Related Items (23)

Optimal approximations made easy ⋮ Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements ⋮ Typical rounding problems ⋮ An elementary approach to lower bounds in geometric discrepancy ⋮ Tight upper bounds for the discrepancy of half-spaces ⋮ Almost optimal set covers in finite VC-dimension ⋮ Approximation and learning of convex superpositions ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Approximating majority depth ⋮ Vapnik-Chervonenkis density in some theories without the independence property. II ⋮ Quasi-Monte-Carlo methods and the dispersion of point sequences ⋮ Set-Codes with Small Intersections and Small Discrepancies ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Reprint of: Approximating majority depth ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ On discrepancy bounds via dual shatter function ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ A lower bound for families of Natarajan dimension \(d\) ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ The VC-dimension of axis-parallel boxes on the torus ⋮ Extending the centerpoint theorem to multiple points ⋮ Norm-graphs: Variations and applications

Cites Work

• Unnamed Item
• Unnamed Item
• \(\epsilon\)-nets and simplex range queries
• New applications of random sampling in computational geometry
• Quasi-optimal range searching in spaces of finite VC-dimension
• On the density of families of sets
• Geometric methods in the study of irregularities of distribution
• Some upper bounds in the theory of irregularities of distribution
• Learnability and the Vapnik-Chervonenkis dimension
• Quasi‐random 2‐ colorings of point sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Discrepancy and approximations for bounded VC-dimension