From the Preface

Questions in discrete geometry typically involve finite sets of points, lines, circles, planes, or other simple geometric objects. For example, one can ask, what is the largest number of regions into which n lines can partition the plane, or what is the minimum possible number of distinct distances occurring among n points in the plane (the former question is easy, the latter one is hard). More complicated objects are investigated too, such as convex polytopes or finite families of convex sets. The emphasis is on ``combinatorial'' properties: which of the given objects intersect, or how many points are needed to intersect all of them, and so on. Characteristics like angle, distance, curvature, or volume, ubiquitous in other areas of geometry, are usually not of primary interest, although they can serve as useful tools.

Many questions in discrete geometry are very natural and worth studying for their own sake. Some of them, such as the structure of 3-dimensional convex polytopes, go back to the Antiquity, and a lot of them are motivated by other areas of mathematics. To a working mathematician or computer scientist, the contemporary discrete geometry offers results and techniques of great diversity, a useful enhancement of the "bag of tricks" for attacking problems in her or his field.

This book is primarily an introductory textbook. It does not require any special background besides the usual undergraduate mathematics (linear algebra, calculus, and a little of combinatorics, graph theory, and probability). It should be accessible to early graduate students, although mastering the more advanced proofs probably needs some mathematical maturity. The first and main part of each section is intended for teaching in class. I have actually taught most of the material, mainly in an advanced course in Prague whose contents varied over the years.

The book can also serve as a collection of surveys in several narrower subfields of discrete geometry where, as far as I know, no adequate recent treatment was available. The sections are accompanied by bibliographic notes and extending remarks. For well-established material, such as convex polytopes, these parts usually refer to the original sources, point to modern treatments and surveys, and present a sample of key results in the area. For the less well-covered topics, I have aimed at surveying most of the important recent results. For some of them, proof outlines are provided, which should convey the main ideas and make it easy to fill in the details from the original source.