Skip to content

Lectures on Discrete Geometry

Spend $50 to get a free DVD!

ISBN-10: 0387953744

ISBN-13: 9780387953748

Edition: 2002

Authors: Jir� Matousek

List price: $84.99
Blue ribbon 30 day, 100% satisfaction guarantee!
Out of stock
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


This book is primarily a textbook introduction to various areas of discrete geometry. In each area it explains several key results and methods in an accessible and concrete manner. It also contains more advanced material in separate sections.
Customers also bought

Book details

List price: $84.99
Copyright year: 2002
Publisher: Springer
Publication date: 5/2/2002
Binding: Paperback
Pages: 486
Size: 6.10" wide x 9.25" long x 1.00" tall
Weight: 3.388
Language: English

Notation and Terminology
Linear and Affine Subspaces, General Position
Convex Sets, Convex Combinations, Separation
Radon's Lemma and Helly's Theorem
Centerpoint and Ham Sandwich
Lattices and Minkowski's Theorem
Minkowski's Theorem
General Lattices
An Application in Number Theory
Convex Independent Subsets
The Erdos Szekeres Theorem
Horton Sets
Incidence Problems
Lower Bounds: Incidences and Unit Distances
Point-Line Incidences via Crossing Numbers
Distinct Distances via Crossing Numbers
Point-Line Incidences via Cuttings
A Weaker Cutting Lemma
The Cutting Lemma: A Tight Bound
Convex Polytopes
Geometric Duality
H-Polytopes and V-Polytopes
Faces of a Convex Polytope
Many Faces: The Cyclic Polytopes
The Upper Bound Theorem
The Gale Transform
Voronoi Diagrams
Number of Faces in Arrangements
Arrangements of Hyperplanes
Arrangements of Other Geometric Objects
Number of Vertices of Level at Most k
The Zone Theorem
The Cutting Lemma Revisited
Lower Envelopes
Segments and Davenport-Schinzel Sequences
Segments: Superlinear Complexity of the Lower Envelope
More on Davenport-Schinzel Sequences
Towards the Tight Upper Bound for Segments
Up to Higher Dimension: Triangles in Space
Curves in the Plane
Algebraic Surface Patches
Intersection Patterns of Convex Sets
The Fractional Helly Theorem
The Colorful Caratheodory Theorem
Tverberg's Theorem
Geometric Selection Theorems
A Point in Many Simplices: The First Selection Lemma
The Second Selection Lemma
Order Types and the Same-Type Lemma
A Hypergraph Regularity Lemma
A Positive-Fraction Selection Lemma
Transversals and Epsilon Nets
General Preliminaries: Transversals and Matchings
Epsilon Nets and VC-Dimension
Bounding the VC-Dimension and Applications
Weak Epsilon Nets for Convex Sets
The Hadwiger-Debrunner (p,q)-Problem
A (p,q)-Theorem for Hyperplane Transversals
Attempts to Count k-sets
Definitions and First Estimates
Sets with Many Halving Edges
The Lovasz Lemma and Upper Bounds in All Dimensions
A Better Upper Bound in the Plane
Two Applications of High-Dimensional Polytopes
The Weak Perfect Graph Conjecture
The Brunn-Minkowski Inequality
Sorting Partially Ordered Sets
Volumes in High Dimension
Volumes, Paradoxes of High Dimension, and Nets
Hardness of Volume Approximation
Constructing Polytopes of Large Volume
Approximating Convex Bodies by Ellipsoids
Measure Concentration and Almost Spherical Sections
Measure Concentration on the Sphere
Isoperimetric Inequalities and More on Concentration
Concentration of Lipschitz Functions
Almost Spherical Sections: The First Steps
Many Faces of Symmetric Polytopes
Dvoretzky's Theorem
Embedding Finite Metric Spaces into Normed Spaces
Introduction: Approximate Emboddings
The Johnson-Lindenstrauss Flattening Lemma
Lower Bounds by Counting
A Lower Bound for the Hamming Cube
A Tight Lower Bound via Expanders
Upper Bounds for l[subscript [infinity]]-Embeddings
Upper Bounds for Euclidean Embeddings
What Was It About? An Informal Summary
Hints to Selected Exercises