Tight upper bounds for the discrepancy of half-spaces

DOI10.1007/BF02574066zbMATH Open0826.68127OpenAlexW2024611484MaRDI QIDQ1892434FDOQ1892434

Authors: Jiří Matoušek 

Publication date: 2 July 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131384

Recommendations

• An \(L^1\) estimate for half-space discrepancy
• Upper bounds in discrepancy theory
• Upper bounds in classical discrepancy theory
• On half-discrete Hilbert's inequality
• A more accurate half-discrete Hilbert-type inequality in the whole plane and the reverses
• scientific article; zbMATH DE number 881165
• A half-discrete Hilbert's inequality
• On a more accurate half-discrete Hilbert's inequality
• A generalization of a half-discrete Hilbert's inequality
• On a half-discrete Mulholland-type inequality

zbMATH Keywords

primal shatter function

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Title not available (Why is that?)
• \(\epsilon\)-nets and simplex range queries
• Title not available (Why is that?)
• Six Standard Deviations Suffice
• Title not available (Why is that?)
• Discrepancy and approximations for bounded VC-dimension
• Quasi-optimal range searching in spaces of finite VC-dimension
• Scale-sensitive dimensions, uniform convergence, and learnability
• Geometric methods in the study of irregularities of distribution
• Roth's estimate of the discrepancy of integer sequences is nearly sharp

Cited In (28)

• Boosting simple learners
• Discrepancy and approximations for bounded VC-dimension
• Discrepancy, chaining and subgaussian processes
• On discrepancy bounds via dual shatter function
• The structure and number of global roundings of a graph
• Typical rounding problems
• An elementary approach to lower bounds in geometric discrepancy
• Two proofs for shallow packings
• The determinant bound for discrepancy is almost tight
• Tighter bounds for the discrepancy of boxes and polytopes
• Improved upper bounds for approximation by zonotopes
• Lower and upper bounds for the waists of different spaces
• Vapnik-Chervonenkis density in some theories without the independence property. I
• Subsampling in smoothed range spaces
• Title not available (Why is that?)
• Discrepancy and sparsity
• Non-independent randomized rounding and coloring
• Bounds for discrepancies in the Hamming space
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Sharp Bounds on the Approximation Rates, Metric Entropy, and n-Widths of Shallow Neural Networks
• Uniform approximation rates and metric entropy of shallow neural networks
• A note on optimal point distributions in \([0,1)^{s}\)
• Extending the centerpoint theorem to multiple points
• The Communication Complexity of Distributed epsilon-Approximations
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• On the gap between hereditary discrepancy and the determinant lower bound
• One-sided epsilon-approximants
• Title not available (Why is that?)

This page was built for publication: Tight upper bounds for the discrepancy of half-spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892434)