Geometric discrepancies are standard measures to quantify the irregularity of distributions. They are an important notion in numerical integration. One of the most important discrepancy notions is the so-called star discrepancy. Roughly speaking, a point set of low star discrepancy value allows for a small approximation error in quasi-Monte Carlo integration. It is thus the most studied discrepancy notion. In this work we present a new algorithm to compute point sets of low star discrepancy. The two components of the algorithm (for the optimization and the evaluation, respectively) are based on evolutionary principles. Our algorithm clearly outperforms existing approaches. To the best of our knowledge, it is also the first algorithm which can be adapted easily to optimize inverse star discrepancies.
Evaluating the star discrepancy of a given point set @math is known to be NP-hard @cite_3 . In fact, it is even W[1]-hard in @math @cite_12 , implying that, under standard complexity assumptions, there is no algorithm to evaluate the star discrepancy of @math points in @math dimension in a running time @math . The best known exact algorithm for evaluating discrepancies, the DEM-algorithm, has a running time of @math @cite_27 . For most relevant settings this is too slow to be applicable. This is true in particular for our setting, where many candidate point sets need to be evaluated. In fact, the complexity of star discrepancy evaluation is the main reason why only few algorithmic approaches are known for the explicit construction of low star discrepancy point sets, cf. also the comment in [page 3] DeRainville2012 .
@cite_27 @cite_12 @cite_3
2162820178 2123331303 2031874716 1508410079
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]. We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. Anal., 34 (1997), pp. 2028-2042] it is based on the optimization algorithm threshold accepting. Our improvements include, amongst others, a nonuniform sampling strategy, which is more suited for higher-dimensional inputs and additionally takes into account the topological characteristics of given point sets, and rounding steps which transform axis-parallel boxes, on which the discrepancy is to be tested, into critical test boxes. These critical test boxes provably yield higher discrepancy values and contain the box that exhibits the maximum value of the local discrepancy. We provide comprehensive experiments to test the new algorithm. Our randomized algorithm computes the exact discrepancy frequently in all cases where this can be checked (i.e., where the exact discrepancy of the point set can be computed in feasible time). Most importantly, in higher dimensions the new method behaves clearly better than all previously known methods. 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. Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. Depending on the ranges, several variants arise, including star discrepancy, box discrepancy, and discrepancy of halfspaces. These problems are solvable in time n^O^(^d^), where d is the dimension of the underlying space. As such a dependency on d becomes intractable for high-dimensional data, we ask whether it can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension, implying that no f(d)@?n^O^(^1^)-time algorithm is possible for any function f(d) unless FPT=W[1]. We also discover the W[1]-hardness of other well known problems, such as determining the largest empty box that contains the origin and is inside the unit cube. This is shown to be hard even to approximate within a factor of 2^n.