An Upper Bound of the Minimal Dispersion via Delta Covers

2017/01/05 by Daniel Rudolf, Rudolf, Daniel · 1 citation
Computer Science · Mathematics · #52B55 #68Q25 #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Numerical Analysis (math.NA) #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.1701.06430

openalex publication_date 2017/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a point set of n elements in the d-dimensional unit cube and a class of test sets we are interested in the largest volume of a test set which does not contain any point. For all natural numbers n, d and under the assumption of a delta-cover with cardinality \vert Γ_δ\vert we prove that there is a point set, such that the largest volume of such a test set without any point is bounded by (log \vert Γ_δ\vert)/(n) + δ. For axis-parallel boxes on the unit cube this leads to a volume of at most (4d)/(n)log((9n)/(d)) and on the torus to (4d)/(n)log (2n).

Cited by

• Minimal dispersion on the sphere

Related

• A tight lower bound on the minimal dispersion
• Minimal dispersion of large volume boxes in the cube
• New bounds on the minimal dispersion
• Lower bounds on the minimal dispersion of point sets via cover-free families
• A note on minimal dispersion of point sets in the unit cube