×

Lectures on discrete geometry. (English) Zbl 0999.52006

Graduate Texts in Mathematics. 212. New York, NY: Springer. xvi, 481 p. (2002).
This is an introduction to the field of discrete geometry understood as the investigation of combinatorial properties of configurations of (usually finitely many) geometric objects, like arrangements of points or hyperplanes or, more generally, convex sets. Some emphasis is laid on asymptotic results which are relevant for estimating the complexity of geometric algorithms. Certain areas of discrete geometry are neglected intentionally, such as the theory of packing and covering. Besides fundamental facts on convex sets, lattice points, and so on, the book deals with the following themes: combinatorial complexity of geometric configurations, intersection patterns and transversals of convex sets, geometric Ramsey theory, polyhedral combinatorics and high-dimensional convexity (including for instance a discussion of volumes in high dimensions and Dvoretzky’s theorem on almost spherical sections), embedding of finite metric spaces into normed spaces. All needed concepts and tools are well explained, in particular the more advanced ones like Gale diagrams, Davenport-Schinzel sequences, and Vapnik-Chervonenkis dimension.
Even some of the more complicated proofs are given in full detail. At the end of each section a comprehensive survey on historical and recent results is presented.
There are also many well-selected exercises, classified according to their difficulty. For some of the exercises hints are given in an appendix.
The book is written in a lively and stimulating but very precise style and contains many figures. It gives a good impression of the richness and the relevance of the field. At the end of the book there is a short summary of each chapter.

MSC:

52A37 Other problems of combinatorial convexity
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52-02 Research exposition (monographs, survey articles) pertaining to convex and discrete geometry
PDFBibTeX XMLCite