Skip to main content

1999 | OriginalPaper | Buchkapitel

Low-Discrepancy Sets for Axis-Parallel Boxes

verfasst von : Jiří Matoušek

Erschienen in: Geometric Discrepancy

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

What should a planar set with small discrepancy for axis-parallel rectangles look like? Maybe the first thing coming to mind would be the regular $$\sqrt n \times \sqrt n$$ grid, placed in the unit square in an appropriate scale, as in Fig. 2.1(a). It is easy to see that this gives discrepancy of the order $$\sqrt n$$. Another attempt might be n independent random points in the unit square as in Fig. 2.1(b), but these typically have discrepancy about $$\sqrt n$$ as well. (In fact, with high probability, the discrepancy is of the order $$\sqrt {n\;\log \;\log \;n} $$; a result well-known to probabilists under the name law of the iterated logarithm comes into play.) It turns out that a far better discrepancy can be achieved, of the order log n. This chapter is devoted to various constructions of such sets and to their higher-dimensional generalizations. In dimension d, for d arbitrary but fixed, the best known sets have discrepancy for axis-parallel boxes of the order logd−1n.

Metadaten
Titel
Low-Discrepancy Sets for Axis-Parallel Boxes
verfasst von
Jiří Matoušek
Copyright-Jahr
1999
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-03942-3_2