Star Discrepancy Benchmark

A new webpage for the Star Discrepancy Subset Selection Problem is available at ALGO

Abstract:

$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 website presents the best known 2D points sets of several sizes with respect to star discrepancy, which were computed with the code available here.