On thel2-discrepancy for anchored boxes

J Matoušek - Journal of Complexity, 1998 - Elsevier
J Matoušek
Journal of Complexity, 1998Elsevier
TheL2-discrepancy for anchored axis-parallel boxes has been used in several recent
computational studies, mostly related to numerical integration, as a measure of the quality of
uniform distribution of a given point set. We point out that if the number of points is not large
enough in terms of the dimension (eg, fewer than 104points in dimension 30) then nearly the
lowest possibleL2-discrepancy is attained by a pathological point set, and hence theL2-
discrepancy may not be very relevant for relatively small sets. Recently, Hickernell obtained …
TheL2-discrepancy for anchored axis-parallel boxes has been used in several recent computational studies, mostly related to numerical integration, as a measure of the quality of uniform distribution of a given point set. We point out that if the number of points is not large enough in terms of the dimension (e.g., fewer than 104points in dimension 30) then nearly the lowest possibleL2-discrepancy is attained by a pathological point set, and hence theL2-discrepancy may not be very relevant for relatively small sets. Recently, Hickernell obtained a formula for the expectedL2-discrepancy of certain randomized low-discrepancy set constructions introduced by Owen. We note that his formula remains valid also for several modifications of these constructions which admit a very simple and efficient implementation. We also report results of computational experiments with various constructions of low-discrepancy sets. Finally, we present a fairly precise formula for the performance of a recent algorithm due to Heinrich for computing theL2-discrepancy.
Elsevier