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

DOI10.1016/j.jco.2011.09.001zbMath1273.11116MaRDI 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

discrepancy; inapproximability; parameterized complexity; geometric dimension; epsilon-nets

Mathematics Subject Classification ID

65Y20: Complexity and performance of numerical algorithms

11K38: Irregularities of distribution, discrepancy

Related Items

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

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