With the advent of readily accessible and powerful computers, algorithmic geometry, renamed as computational geometry, has flourished. It is now an active area of geometry, with manifold applications: from computer graphics, computed assisted designs, robotics and even to the global positioning systems, that GPS device that we carry in our phones or cars.
The book under review is an accessible introduction to computational geometry assuming a basic mathematical background on linear algebra and calculus. Being an introduction, the authors have selected some topics that are within the reach of an advanced undergraduate student of mathematics, computer science or engineering. The topics range from convex geometry to elementary algebraic geometry and include some applications. Therefore, the book is naturally divided in three parts.
The first part focuses on linear geometry, meaning that the geometric objects are given by systems of linear equations or inequalities. Thus, many of the algorithms in this part are somehow variations of the familiar Gaussian elimination or the simplex method of linear optimization.
The second part considers geometric objects given as zeros of systems of polynomial equations in affine space. In other words, the focus is on some elementary aspects of computational algebraic geometry. Most of the algorithms in this part are based on the Buchberger’s algorithm to find a Gröbner basis of the ideal that defines the given affine variety.
The third and last part of the book explores some applications, for example the reconstruction of a plane curve given a finite set of points of the curve that are sufficiently close together. The last application, to the GPS, which as we all are aware gives the position of an object on our planet with great accuracy and is based on signals from some satellites orbiting the Earth. As it happens, and it is explained in the last section of the book under review, signals from at least four satellites are required. Using these signals the GPS device measures its distance to the satellites. With these distances we get at least four spheres and the position of the GPS device is given as one of the solutions of the classical Apollonius problem for the given spheres. It is indeed a beautiful way to end the book, with an application of a classical theorem to an everyday device!
As one may expect from a book on computational geometry, the book uses and discusses not only the algorithms and their complexity, but also the implementations of these algorithms. The software discussed range from commercial software to open-source software such as polymake, Singular or Sage.
This is a beautiful book, full with examples, algorithms, color graphics and on top of that it is printed on fine quality paper to better appreciate the color plates. As I mentioned before, the book can be used by an interested mathematics or computer science major for a selected topics course or for self-study.
Felipe Zaldivar is Professor of Mathematics at the Universidad Autonoma Metropolitana-I, in Mexico City. His e-mail address is firstname.lastname@example.org.