Matousek J. Lectures on Discrete Geometry 2002

Download this torrent!

Matousek J. Lectures on Discrete Geometry 2002

Textbook in PDF format The next several pages describe the goals and the main topics of this book. 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. 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 many of them are motivated by other areas of mathematics. To a working mathematician or computer scientist, 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. My experience in this respect comes mainly from combinatorics and the design of efficient algorithms, where, as time progresses, more and more of the first-rate results are proved by methods drawn from seemingly distant areas of mathematics and where geometric methods are among the most prominent