E-Book, Englisch, Band 18, 296 Seiten, eBook
Reihe: Algorithms and Combinatorics
Matousek Geometric Discrepancy
1999
ISBN: 978-3-642-03942-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
An Illustrated Guide
E-Book, Englisch, Band 18, 296 Seiten, eBook
Reihe: Algorithms and Combinatorics
ISBN: 978-3-642-03942-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
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? This book is an accessible and lively introduction to the area of geometric discrepancy theory, with numerous exercises and illustrations. In separate, more specialized parts, it also provides a comprehensive guide to recent research.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
1. Introduction 1.1 Discrepancy for Rectangles and Uniform Distribution 1.2 Geometric Discrepancy in a More General Setting 1.3 Combinatorial Discrepancy 1.4 On Applications and Connections 2. Low-Discrepancy Sets for Axis-Parallel Boxes 2.1 Sets with Good Worst-Case Discrepancy 2.2 Sets with Good Average Discrepancy 2.3 More Constructions: b-ary Nets 2.4 Scrambled Nets and Their Average Discrepancy 2.5 More Constructions: Lattice Sets 3. Upper Bounds in the Lebesgue-Measure Setting 3.1 Circular Discs: a Probabilistic Construction 3.2 A Surprise for the L 1-Discrepancy for Halfplanes 4. Combinatorial Discrepancy 4.1 Basic Upper Bounds for General Set Systems 4.2 Matrices, Lower Bounds, and Eigenvalues 4.3 Linear Discrepancy and More Lower Bounds 4.4 On Set Systems with Very Small Discrepancy 4.5 The Partial Coloring Method 4.6 The Entropy Method 5. VC-Dimension and Discrepancy 5.1 Discrepancy and Shatter Functions 5.2 Set Systems of Bounded VC-Dimension 5.3 Packing Lemma 5.4 Matchings with Low Crossing Number 5.5 Primal Shatter Function and Partial Colorings 6. Lower Bounds 6.1 Axis-Parallel Rectangles: L 2-Discrepancy 6.2 Axis-Parallel Rectangles: the Tight Bound 6.3 A Reduction: Squares from Rectangles 6.4 Halfplanes: the Combinatorial Discrepancy 6.5 Combinatorial Discrepancy for Halfplanes Revisited 6.6 Halfplanes: the Lebesgue-Measure Discrepancy 6.7 A Glimpse of Positive Definite Functions 7. More Lower Bounds and the Fourier Transform 7.1 Arbitrarily Rotated Squares 7.2 Axis-Parallel Cubes 7.3 An Excursion to Euclidean Ramsey Theory A. Tables of Selected Discrepancy Bounds Bibliography Index Hints
