Browse Books

Reviewer: Piyush Kumar

Research in discrete geometry in the past few years has increasingly been motivated by applications in computational geometry and combinatorial optimization, as well as in other fields like graphics, geographic information systems (GIS), data mining, machine learning, and computational biology. In fact, a grasp of some parts of discrete geometry might be essential in understanding some concepts in these fields. However, there are various problems in discrete geometry that are of interest in their own right, and that have been studied by mathematicians for a long time. For a computer scientist, discrete geometry offers a tool chest that enhances the power to solve problems in various fields. This is an introductory text on discrete geometry. The author covers a wide variety of topics, which, according to the author, can be grouped into seven areas: foundations; combinatorial complexity of geometric configurations; intersection patterns and traversals of convex sets; geometric Ramsey theory; polyhedral combinatorics and high dimensional convexity; and representing finite metric spaces by coordinates. The book itself contains 15 chapters. Chapters 13 and 14 cover “Volumes In High Dimensions” and “Measure Concentration and Almost Spherical Sections.” I found these chapters to be less interesting than the others, since I have been exposed to Keith Ball’s masterpiece [1] on the subject. Chapter 12, on applications of high dimensional polytopes, also has material overlapping Ball’s introduction [1]. The rest of the 12 chapters seemed essential. The fifteenth chapter, “Embedding Finite Metric Spaces Into Normed Spaces,” presents some of the best coverage of the subject I’ve seen. This chapter deals with the question of embedding an n-point metric space into Euclidean space, such that the Euclidean distances approximate the given distances in the finite metric space. This is one of the emerging tools to handle the “curse of dimensionality” problem in various areas. What follows is my attempt at a short summary of the first 11 chapters of the book, offering a glimpse of what other material to expect in the chapter: Chapter 1, “Convexity Theory,” includes concepts such as convex set and centerpoints, and theorems like separation, Helly, Radon, and Caratheodory. Chapter 2, “Lattices and Minkowski’s theorem,” covers general lattice and Minkowski’s theorem for general lattices. Chapter 3, “Convex Independent Subsets,” covers Erodos-Szekeres theorem and k-holes. Chapter 4, “Incidence Problems,” addresses Szemeredi-Trotter, crossing number, and cutting lemma. Chapter 5, “Convex Polytopes,” covers geometric duality, convex hulls and polytopes, Gale transform, and Voronoi diagrams. Chapter 6, “Number of Faces in Arrangements,” includes Clarkson’s theorem on levels, zone theorem, and Milnor-Thom theorem. Chapter 7, “Lower envelopes,” covers Davenport-Schinzel sequences and lower envelopes of surface patches. Chapter 8, “Intersection Pattern of Convex Sets,” includes material on fractional Helly theorem, Caratheodory, and Tverberg’s theorems with their colored counterparts. Chapter 9, “Geometric Selection Theorems,” covers order type and hypergraph regularity lemma. Chapter 10, “Traversals and Epsilon Nets,” covers set systems, epsilon nets, VC-dimension, weak epsilon nets, and Alon-Kleitman theorem. Finally, chapter 11, “Attempt To Count k-sets,” covers k-sets, k-facets, and Lovasz’ lemma. The book is suitable as a textbook in a graduate course, perhaps in computational geometry, assuming that students have taken a basic course in computational geometry using one of the standard textbooks [2]. It would be appropriate for either computer science or math students. Some advanced material could be assigned for self-study, and would attract researchers. A reader knowledgeable in the field and interested in a particular topic could also jump in and read a single chapter. The chapters could be used for independent study as surveys of narrower fields. There are ample exercises in the book. There are a few typographical errors, which should be noted soon on the book’s Web page. The index is quite well suited for searching for a particular topic in the book, and the references are very up to date. All in all, this is an unusual work, from an extraordinary researcher. I highly recommend it, both as a textbook, and as an interesting read for anyone who is interested in learning the tricks and traps of discrete geometry. Online Computing Reviews Service

Reviewer: Toshiro Kubota

An interesting tutorial on discrete geometry is presented in this book. It is intended for use as a textbook, for either mathematics or computer science students, and is quite readable, even for those without much mathematical background. From a computer scientist’s point of view, the text would be appropriate as a supplemental textbook for courses on computational geometry, combinatorial optimization, and robotics, in which the focus is not only on the algorithmic and computational aspects, but also on the fundamental mathematical understanding of algorithms. Such emphasis on fundamental theory and mathematical rigor is often missing in today’s curriculum, partially due to lack of proper textbooks in many subject areas. Matousek’s book is purely mathematical, but not excessively mathematical for computer science students, and he introduces many concepts smoothly, and weaves them into more complex forms. What I like about introducing fundamental discrete geometry to computer science courses is the following: many problems in discrete geometry are easier to grasp than other, more abstract, mathematical problems. For example: “how many regions can a plane be partitioned into by N lines__?__” or, “which shape with a fixed surface area has the highest volume__?__” However, students need to expand their thinking to dimensions much higher than three. Such high-dimensional thinking is essential in solving complex problems and exploring new algorithms, and discrete geometry encourages the practice in a more natural way than other more abstract areas of study, such as Hilbert space and quantum computing. The book starts with a very concise introduction to mathematical notations and definitions in sets, vector space, graphs, topology, probability, and various inequalities, in just two pages. It then introduces classical theorems, such as Radon, Helly, Caratheodory, Minkowski, and Erdos-Szekeres, while introducing basic geometrical concepts, such as affine space, convexity, lattice, polytopes, and simplices, along the way. This fundamental part of the book takes up the first seven chapters. The next three chapters (chapters 8 to 10) extend some of the fundamental results, and use them to prove the so called ( p,q )-theorem. Along the way, the author introduces VC-dimension, which has gained a significant amount of interest in the machine learning and pattern recognition communities, and which determines the dimensions of some simple cases. Chapter 11 introduces k -set problem, and stands it own. This is a challenging problem, and the author provides a glimpse of the current state in this subject. The next three chapters (chapters 12 to 14) are concerned with high-dimensional problems in convex geometry. In the preface, the author compares these chapters with a well-known lecture note by Keith Ball [1], and humbly acknowledges a more graceful form of the Ball’s work. Although these chapters overlap substantially with Ball’s lecture note, which is a m ore clear-cut exposition of the material, they can serve as a better introduction for computer scientists; less mathematical background is needed to follow the proofs in Matousek’s work than in Ball’s, and Matousek often relates his discussion to familiar data structures, such as graphs, nets, and ordered lists. The last chapter is devoted to the problem of embedding a metric space in a normed space, in particular a Euclidean space. For example, how can N points in a higher dimension be mapped to a plane so that the distance between every pair of points undergoes as small distortion as possible__?__ This is a very current problem in statistics, data visualization and mining, and machine learning, to name a few. The author provides up-to-date theoretical bounds on various embedding cases. As in the rest of the book, the chapter is focused on the mathematics, and does not discuss anything about how to do the embedding computationally (not even the classical multi-dimensional scaling). Readers who are familiar with the practical aspects of the problem, however, will find the chapter stimulating, as the author exquisitely exhibits Linial-London-Rabinovich theorem and Bourgain’s theorem. The references in the book are extremely up-to-date, and each section concludes with bibliography, along with remarks that provide further information on relevant topics and more recent works. I found the reverse indexing of the references (to show the page number of where each reference appears) to be convenient. The book provides a number of exercise problems at the end of each section. The author has maintained an accompanying Web page for errata. Overall, I found this to be an exceptional book on the subject. As the author admits, the topics covered here are not exhaustive, and some important topics are not touched on, such as Brouwer’s fixed point theorem and Kepler’s problem (although Kepler’s problem is indirectly addressed in chapter 13, “Volumes in high dimensions”). The organization of the book can also be slightly confusing at first. However, the author has done an excellent job of covering the subject in a clear manner. Online Computing Reviews Service