Expected dispersion of uniformly distributed points

DOI10.1016/J.JCO.2020.101483MaRDI QIDQ1996876zbMATH OpenOpenAlexFDO

Authors Aicke Hinrichs, David Krieg, Robert J. Kunsch, Daniel Rudolf

Publication date 26 February 2021

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

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

zbMATH Keywords

dispersiondelta coverexpected dispersion

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Combinatorial aspects of finite geometries (05B25) Combinatorial geometries and geometric closure systems (51D20)

Abstract: The dispersion of a point set in $[0,1{]}^d$ is the volume of the largest axis parallel box inside the unit cube that does not intersect with the point set. We study the expected dispersion with respect to a random set of $n$ points determined by an i.i.d. sequence of uniformly distributed random variables. Depending on the number of points $n$ and the dimension $d$ we provide an upper and lower bound of the expected dispersion. In particular, we show that the minimal number of points required to achieve an expected dispersion less than $varepsilonin(0,1)$ depends linearly on the dimension $d$.

Recommendations

• An upper bound on the minimal dispersion
• Deterministic constructions of high-dimensional sets with small dispersion
• New bounds on the minimal dispersion
• A note on minimal dispersion of point sets in the unit cube
• The minimal \(k\)-dispersion of point sets in high dimensions

Cites work

• scientific article; zbMATH DE number 3550803 (Why is no real title available?)
• 6. Fibonacci lattices have minimal dispersion on the two-dimensional torus
• A lower bound for the dispersion on the torus
• A note on minimal dispersion of point sets in the unit cube
• An upper bound of the minimal dispersion via delta covers
• An upper bound on the minimal dispersion
• Approximation of high-dimensional rank one tensors
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Limiting distribution of the maximal distance between random points on a circle: a moments approach
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On the dispersion of sparse grids
• On the fixed volume discrepancy of the Fibonacci sets in the integral norms
• On the size of the largest empty box amidst a point set
• Quasi-Monte-Carlo methods and the dispersion of point sequences
• Recovery algorithms for high-dimensional rank one tensors
• Tractability of the approximation of high-dimensional rank one tensors
• Universal discretization

Cited in

(12)

• The minimal \(k\)-dispersion of point sets in high dimensions
• A tight lower bound on the minimal dispersion
• A note on minimal dispersion of point sets in the unit cube
• An upper bound on the minimal dispersion
• Deterministic constructions of high-dimensional sets with small dispersion
• New bounds on the minimal dispersion
• Efficient algorithms for discrepancy minimization in convex sets
• The minimal spherical dispersion
• Minimal dispersion on the cube and the torus
• A remark on the minimal dispersion
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy

This page was built for publication: Expected dispersion of uniformly distributed points

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