1999 | OriginalPaper | Buchkapitel
Low-Discrepancy Sets for Axis-Parallel Boxes
verfasst von : Jiří Matoušek
Erschienen in: Geometric Discrepancy
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.