Deterministic constructions of high-dimensional sets with small dispersion

DOI10.1007/S00453-022-00943-XzbMATH Open1492.68135arXiv1901.06702OpenAlexW2914990731MaRDI QIDQ2149098FDOQ2149098

Jan Vybíral, Mario Ullrich

Publication date: 28 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The dispersion of a point set $Psubset[0,1{]}^d$ is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect $P$. Here, we show a construction of low-dispersion point sets, which can be deduced from solutions of certain $k$-restriction problems, which are well-known in coding theory. It was observed only recently that, for any $varepsilon>0$, certain randomized constructions provide point sets with dispersion smaller than $varepsilon$ and number of elements growing only logarithmically in $d$. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in $d$. Note that, however, the running-time will be super-exponential in $varepsilo{n}^{-1}$.

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

Recommendations

• An upper bound on the minimal dispersion
• New bounds on the minimal dispersion
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Expected dispersion of uniformly distributed points
• The minimal \(k\)-dispersion of point sets in high dimensions

zbMATH Keywords

dispersionhigh dimensionserror-correcting codesexplicit construction

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Irregularities of distribution, discrepancy (11K38) Bounds on codes (94B65) Combinatorial geometries and geometric closure systems (51D20)

Cites Work

• Title not available (Why is that?)
• Sequences, discrepancies and applications
• Families of \(k\)-independent sets
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Approximate formulas for some functions of prime numbers
• Algorithmic construction of sets for k -restrictions
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Discrepancy Theory and Quasi-Monte Carlo Integration
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• Efficient approximation of product distributions
• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• On the largest empty axis-parallel box amidst \(n\) points
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• 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
• Explicit construction of exponential sized families of k-independent sets
• Vector sets for exhaustive testing of logic circuits
• Computing the Largest Empty Rectangle
• On the maximum empty rectangle problem
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• A remark on the minimal dispersion
• Calculation of Discrepancy Measures and Applications
• The Marcinkiewicz-type discretization theorems
• On the dispersion of sparse grids
• Title not available (Why is that?)
• Global Stochastic Optimization with Low-Dispersion Point Sets
• 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
• Some Results on the Complexity of Numerical Integration
• The minimal \(k\)-dispersion of point sets in high dimensions
• Maximal empty boxes amidst random points
• On the number of maximum empty boxes amidst \(n\) points
• Recovery algorithms for high-dimensional rank one tensors

Cited In (3)

• Deterministic construction of a high dimensional l _p section in l ₁ ⁿ for any p <2
• Title not available (Why is that?)
• Reconstructive dispersers and hitting set generators

This page was built for publication: Deterministic constructions of high-dimensional sets with small dispersion

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