Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combinatorial discrepancy. Depending on the ranges, several possible variants arise, for example star discrepancy, box discrepancy, and discrepancy of half-spaces. In this paper, we investigate the hardness of these problems with respect to the dimension d of the underlying space. All these problems are solvable in time n^O(d) , but such a time dependency quickly becomes intractable for high-dimensional data. Thus it is interesting to ask whether the dependency on d can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension. This is done via a parameterized reduction from the Clique problem. As the parameter stays linear in the input parameter, the results moreover imply that these problems require n^ (d) time, unless 3-Sat can be solved in 2^o(n) time. Further, we derive that testing whether a given set is an -net with respect to half-spaces takes n^ (d) time under the same assumption. As intermediate results, we discover the W[1]-hardness of other well known problems, such as determining the largest empty star inside the unit cube. For this, we show that it is even hard to approximate within a factor of 2^n .
In the first part of this paper we derive lower bounds and constructive upper bounds for the bracketing numbers of anchored and unanchored axis-parallel boxes in the d-dimensional unit cube. In the second part we apply these results to geometric discrepancy. We derive upper bounds for the inverse of the star and the extreme discrepancy with explicitly given small constants and an optimal dependence on the dimension d, and provide corresponding bounds for the star and the extreme discrepancy itself. These bounds improve known results from [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star-discrepancy via @d-covers, J. Complexity 21 (2005) 691-709], [M. Gnewuch, Bounds for the average L^p-extreme and the L^ -extreme discrepancy, Electron. J. Combin. 12 (2005) Research Paper 54] and [H. N. Mhaskar, On the tractability of multivariate integration and approximation by neural networks, J. Complexity 20 (2004) 561-590]. We also discuss an algorithm from [E. Thiemard, An algorithm to compute bounds for the star discrepancy, J. Complexity 17 (2001) 850-880] to approximate the star-discrepancy of a given n-point set. Our lower bound on the bracketing number of anchored boxes, e.g., leads directly to a lower bound of the running time of Thiemard's algorithm. Furthermore, we show how one can use our results to modify the algorithm to approximate the extreme discrepancy of a given set.  The well-known star discrepancy is a common measure for the uniformity of point distributions. It is used, e.g., in multivariate integration, pseudo random number generation, experimental design, statistics, or computer graphics. We study here the complexity of calculating the star discrepancy of point sets in the d-dimensional unit cube and show that this is an NP-hard problem. To establish this complexity result, we first prove NP-hardness of the following related problems in computational geometry: Given n points in the d-dimensional unit cube, find a subinterval of minimum or maximum volume that contains k of the n points. Our results for the complexity of the subinterval problems settle a conjecture of E. Thiemard [E. Thiemard, Optimal volume subintervals with k points and star discrepancy via integer programming, Math. Meth. Oper. Res. 54 (2001) 21-45]. Patterns used for supersampling in graphics have been analyzed from statistical and signal-processing viewpoints. We present an analysis based on a type of isotropic discrepancy—how good patterns are at estimating the area in a region of defined type. We present algorithms for computing discrepancy relative to regions that are defined by rectangles, halfplanes, and higher-dimensional figures. Experimental evidence shows that popular supersampling patterns have discrepancies with better asymptotic behavior than random sampling, which is not inconsistent with theoretical bounds on discrepancy.