New bounds on the minimal dispersion

DOI10.1016/j.jco.2022.101648zbMath1497.51004arXiv2108.10374OpenAlexW4206287781MaRDI QIDQ2145076

Galyna V. Livshyts, Alexander E. Litvak

Publication date: 17 June 2022

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.10374

zbMATH Keywords

complexitytorusminimal dispersionlargest empty box\(k\)-dispersion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Length, area and volume in real or complex geometry (51M25) Complexity and performance of numerical algorithms (65Y20) Combinatorial geometries and geometric closure systems (51D20) Asymptotic theory of convex bodies (52A23)

Related Items

Minimal dispersion of large volume boxes in the cube ⋮ The minimal spherical dispersion

Cites Work

• Unnamed Item
• Unnamed Item
• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
• A note on minimal dispersion of point sets in the unit cube
• On the dispersion of sparse grids
• An upper bound on the minimal dispersion
• A note on the dispersion of admissible lattices
• The minimal \(k\)-dispersion of point sets in high dimensions
• Quasi-Monte-Carlo methods and the dispersion of point sequences
• On the largest empty axis-parallel box amidst \(n\) points
• Expected dispersion of uniformly distributed points
• A lower bound for the dispersion on the torus
• The VC-dimension of axis-parallel boxes on the torus
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• Minimal dispersion of large volume boxes in the cube
• On the size of the largest empty box amidst a point set
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• A note on coverings
• Learnability and the Vapnik-Chervonenkis dimension
• Covering convex bodies by translates of convex bodies
• An Upper Bound of the Minimal Dispersion via Delta Covers
• A remark on the minimal dispersion
• Empty Axis-Parallel Boxes