Expected dispersion of uniformly distributed points

DOI10.1016/J.JCO.2020.101483zbMATH Open1456.60042arXiv1911.12074OpenAlexW3014655380MaRDI QIDQ1996876FDOQ1996876

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)

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$.

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

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

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)

Cites Work

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

Cited In (12)

• A tight lower bound on the minimal dispersion
• The minimal \(k\)-dispersion of point sets in high dimensions
• 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)