On the dispersion of sparse grids

DOI10.1016/J.JCO.2017.11.005MaRDI QIDQ1704609zbMATH OpenOpenAlexFDO

Authors David Krieg

Publication date 12 March 2018

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

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

zbMATH Keywords

dispersionhigh-dimensional problemssparse gridlargest empty box

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial geometries and geometric closure systems (51D20)

Abstract: For any natural number $d$ and positive number $varepsilon$, we present a point set in the $d$-dimensional unit cube $[0,1{]}^d$ that intersects every axis-aligned box of volume greater than $varepsilon$. These point sets are very easy to handle and in a vast range for $varepsilon$ and $d$, we do not know any smaller set with this property.

Recommendations

• Sparse grids
• scientific article; zbMATH DE number 66109
• scientific article; zbMATH DE number 877099
• Sparse grids and related approximation schemes for higher dimensional problems
• Optimal scaling parameters for sparse grid discretizations.
• Selected Recent Applications of Sparse Grids
• Multigrid for discrete differential forms on sparse grids
• On applicability of the sparse grid method in the worst case setting
• scientific article; zbMATH DE number 1301767

Cites work

• A note on minimal dispersion of point sets in the unit cube
• An upper bound on the minimal dispersion
• Learnability and the Vapnik-Chervonenkis dimension
• On the largest empty axis-parallel box amidst \(n\) points
• On the size of the largest empty box amidst a point set
• Quasi-Monte-Carlo methods and the dispersion of point sequences
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of the approximation of high-dimensional rank one tensors

Cited in

(24)

• A note on the dispersion of admissible lattices
• The minimal \(k\)-dispersion of point sets in high dimensions
• A tight lower bound on the minimal dispersion
• Expected dispersion of uniformly distributed points
• Improved dispersion bounds for modified Fibonacci lattices
• On the fixed volume discrepancy of the Fibonacci sets in the integral norms
• Piercing all translates of a set of axis-parallel rectangles
• Minimal dispersion of large volume boxes in the cube
• Universal discretization
• A note on minimal dispersion of point sets in the unit cube
• An upper bound on the minimal dispersion
• Measure-based diffusion grid construction and high-dimensional data discretization
• An upper bound of the minimal dispersion via delta covers
• Deterministic constructions of high-dimensional sets with small dispersion
• Spurious scattering from discontinuously stretching grids in computational fluid dynamics
• New bounds on the minimal dispersion
• The exponent of discrepancy of sparse grids is at least 2. 1933
• Uniformly Spread Discrete Sets in R ^d
• Recovery algorithms for high-dimensional rank one tensors
• A remark on the minimal dispersion
• Selected Recent Applications of Sparse Grids
• Sparse grids
• Piercing all translates of a set of axis-parallel rectangles
• The area of empty axis-parallel boxes amidst 2-dimensional lattice points

This page was built for publication: On the dispersion of sparse grids

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