Deterministic constructions of high-dimensional sets with small dispersion

DOI10.1007/S00453-022-00943-XMaRDI QIDQ2149098zbMATH OpenOpenAlexFDO

Authors Mario Ullrich, Jan Vybíral

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 1512071 (Why is no real title available?)
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Reconstructive dispersers and hitting set generators
• Deterministic construction of a high dimensional l _p section in l ₁ ⁿ for any p <2
• Expected dispersion of uniformly distributed points

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)