Star Discrepancy Benchmark
$L_{\infty}$ star discrepancy of a $n$-point set $P \subseteq [0,1]^d$ measures how well the volume of a $d$-dimensional box of the form $[0,q]$ can be approximated by the fraction $|P \cap [0,q]|/|P|$ of points that fall inside this box. More precisely, it measures the largest such deviation between volume and fraction of points. Point sets of low star discrepancy have several important applications, among them Quasi-Monte Carlo integration, one-shot optimization, financial mathematics, design of experiments, and many more. The design of point sets which guarantee small discrepancy values has been an intensively studied topic in numerical analysis in the last decades, and several constructions are known which achieve smaller $L_{\infty}$ star discrepancy than randomly sampled points.
The following table presents the best known two-dimensional points sets of several sizes with respect to star discrepancy. The values are rounded to the sixth decimal place and were computed with the code available here.
If you would like to contribute to this benchmark and if you have published your method to generate the point set, please, send us an email. If you write a article describing research that made substantive use of these point sets, please, mention the reference that is available in the table.
| Size | Value | Plot | Reference |
|---|---|---|---|
| 20 | 0.073086 Download |  |
[1] |
| 40 | 0.044444 Download |  |
[1] |
| 60 | 0.032772 Download |  |
[1] |
| 80 | 0.027148 Download |  |
[1] |
| 100 | 0.022964 Download |  |
[1] |
| 120 | 0.019856 Download |  |
[1] |
References
[1] F. Clèment, C. Doerr, L. Paquete, “Star Discrepancy Subset Selection: Problem Formulation and Efficient Approaches for Low Dimensions”, arXiv:2101.07881