Geometric Discrepancy

by Matousek, Jiri

• ISBN13: 9783540655282
• ISBN10: 354065528X
• Format: Hardcover
• Copyright: 1999-06-01
• Publisher: Springer Verlag

Summary

What is the "most uniform" way of distributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? Such questions are treated in geometric discrepancy theory. The book is an accessible and lively introduction to this area, with numerous exercises and illustrations. In separate, more specialized parts, it also provides a comprehensive guide to recent research. Including a wide variety of mathematical techniques (from harmonic analysis, combinatorics, algebra etc.) in action on non-trivial examples, the book is suitable for a "special topic" course for early graduates in mathematics and computer science. Besides professional mathematicians, it will be of interest to specialists in fields where a large collection of objects should be "uniformly" represented by a smaller sample (such as high-dimensional numerical integration in computational physics or financial mathematics, efficient divide-and-conquer algorithms in computer science, etc.).

Table of Contents

Preface	v
Notation	xi
Introduction	1	(36)
Discrepancy for Rectangles and Uniform Distribution	1	(8)
Geometric Discrepancy in a More General Setting	9	(7)
Combinatorial Discrepancy	16	(6)
On Applications and Connections	22	(15)
Low-Discrepancy Sets for Axis-Parallel Boxes	37	(46)
Sets with Good Worst-Case Discrepancy	38	(6)
Sets with Good Average Discrepancy	44	(7)
More Constructions: b-ary Nets	51	(10)
Scrambled Nets and Their Average Discrepancy	61	(11)
More Constructions: Lattice Sets	72	(11)
Upper Bounds in the Lebesgue-Measure Setting	83	(18)
Circular Discs: a Probabilistic Construction	84	(9)
A Surprise for the L1-Discrepancy for Halfplanes	93	(8)
Combinatorial Discrepancy	101	(36)
Basic Upper Bounds for General Set Systems	101	(4)
Matrices, Lower Bounds, and Eigenvalues	105	(4)
Linear Discrepancy and More Lower Bounds	109	(8)
On Set Systems with Very Small Discrepancy	117	(3)
The Partial Coloring Method	120	(8)
The Entropy Method	128	(9)
VC-Dimension and Discrepancy	137	(34)
Discrepancy and Shatter Functions	137	(8)
Set Systems of Bounded VC-Dimension	145	(10)
Packing Lemma	155	(4)
Matchings with Low Crossing Number	159	(5)
Primal Shatter Function and Partial Colorings	164	(7)
Lower Bounds	171	(42)
Axis-Parallel Rectangles: L2-Discrepancy	172	(4)
Axis-Parallel Rectangles: the Tight Bound	176	(4)
A Reduction: Squares from Rectangles	180	(2)
Halfplanes: Combinatorial Discrepancy	182	(11)
Combinatorial Discrepancy for Halfplanes Revisited	193	(4)
Halfplanes: the Lebesgue-Measure Discrepancy	197	(6)
A Glimpse of Positive Definite Functions	203	(10)
More Lower Bounds and the Fourier Transform	213	(28)
Arbitrarily Rotated Squares	213	(17)
Axis-Parallel Cubes	230	(4)
An Excursion to Euclidean Ramsey Theory	234	(7)
A. Tables of Selected Discrepancy Bounds	241	(4)
Bibliography	245	(20)
Index	265	(10)
Hints	275