Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension

DOI10.1016/j.jco.2011.09.001zbMath1273.11116OpenAlexW1508410079MaRDI QIDQ413466

Magnus Wahlström, Christian Knauer, Daniel Werner, Panos Giannopoulos

Publication date: 7 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.jco.2011.09.001

zbMATH Keywords

discrepancyinapproximabilityparameterized complexitygeometric dimensionepsilon-nets

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Irregularities of distribution, discrepancy (11K38)

Related Items

Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ An enumerative formula for the spherical cap discrepancy ⋮ Probabilistic discrepancy bound for Monte Carlo point sets ⋮ Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples ⋮ On the number of maximum empty boxes amidst \(n\) points ⋮ Calculation of Discrepancy Measures and Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Sequences, discrepancies and applications
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• \(\epsilon\)-nets and simplex range queries
• An algorithm to compute bounds for the star discrepancy
• The maximum box problem and its application to data analysis
• On the largest empty axis-parallel box amidst \(n\) points
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Geometric clustering
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• On Approximating the Depth and Related Problems
• Tight lower bounds for the size of epsilon-nets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Geometric discrepancy. An illustrated guide