On theL2-Discrepancy for Anchored Boxes
Author: Matoušek, J.
Source: Journal of Complexity, Volume 14, Number 4, December 1998 , pp. 527-556(30)
Publisher: Academic Press
Abstract: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.
Document Type: Research Article
Affiliations: Department of Applied Mathematics, Charles University, Malostranské nám. 25, Prague 1, 118 00, Czech Republic
Publication date: December 1, 1998