Handbook of Discrete and Computational Geometry ed. by Jacob E. Goodman and Joseph O'Rourke

This laptop of a handbook is a tremendous collection of 65 articles on discrete and computational geometry. The second edition, at 1539 pages, is more than 500 pages longer than the first. The organization of the book is superb. Each article/chapter begins with an introduction and ends with lists of recommended surveys and related chapters, as well as comprehensive references. In addition, each chapter contains one or more glossaries. When a chapter contains more than a single glossary, each glossary precedes a corresponding section of the chapter. The book ends with two indices: one of the cited authors, the other of the defined terms. Chapters (and often individual sections) are supplemented with lists of open problems. If I were to make a structural recommendation, I would suggest that each chapter be preceded by a table of contents. The glossaries are helpful for grasping the contents at a glance, but they do not reflect on the structure of the chapters accurately. Further, the glossaries are not usually ordered alphabetically.

The book consists of seven parts. The first two — COMBINATORIAL AND DISCRETE GEOMETRY and POLYTOPES AND POLYHEDRA — deal with fundamental geometric objects and tasks, such as finite point configurations, lattices, tilings, packings, arrangements, linkages, skeletons, triangulation, complexes, etc. The third part — ALGORITHMS AND COMPLEXITY OF FUNDAMENTAL GEOMETRIC OBJECTS — discusses geometric objects from a computational point of view. The fourth and fifth parts — GEOMETRIC DATA STRUCTURES AND SEARCHING and COMPUTATIONAL TECHNIQUES — procede with the specifics of the computational aspects, like efficient data structures for searching, point location, parallel algorithms in geometry, robustness of geometric computations, collision detection, etc. The sixth part — APPLICATIONS OF DISCRETE AND COMPUTATIONAL GEOMETRY — deals with applications ranging from applied mathematics (linear and mathematical programming) through applications of computational topology to stuctural molecular biology.

The sixth part is the largest in the book. Nonetheless, various applications are discussed briefly throughout the volume. For example, applications of linkages to engineering and biology are mentioned at the end of Chapter 9, Geometry and Topology of Polygonal Linkages (part 1). Chapter 33, Computational Real Algebraic Geometry (part 3), highlights its connections to robot motion planning, solid modeling and geometric theorem proving. Chapter 35, Collision and Proximity Queries (part 4) describes a startling application to virtual exploration of a digestive system.

The last chapter introduces two computational geometry libraries, LEDA and CGAL. The penultimate chapter provides a broad review of the relevant software. In particular, it includes several references to the web sources. These two chapters comprise the seventh part of the book — GEOMETRIC SOFTWARE.

Most of the book is written in a concise, often formal, manner: an introduction, the terms, a list of theorems or main results, a list of open problems, that of related chapters, references. But sometimes a chapter takes a gentler approach. I especially liked Chapter 14, Topological Methods. The introduction has been extended over several sections that bring together recent applications of algebraic topology (the earliest references are from the 1990s) with age-old results such as the Ham Sandwitch and Barsuk-Ulam Theorems.

Topological methods apply to the study of the global structure of an object or the configuration space associated with a problem. Manifolds and simplicial complexes serve as typical examples of configuration spaces. The global properties of configuration spaces are captured in terms of their homology and homotopy groups. Computational Topology (Chapter 32) deals with the complexity of such problems and the development of efficient algorithms for their solution.

The book is the fruit of the collaboration of an illustrious team of eighty two authors brought together by two foremost mathematicians in the field. Jacob E. Goodman, is an Editor-in-Chief of the prominent journal of Discrete & Computational Geometry. Joseph O'Rourke is a notable computer scientist and a distinguished expositor with two exceptionally lucid books to his credit. One of these, Computational Geometry in C, serves as an excellent companion to the book under review.

The Handbook of Discrete and Computational Geometry is intended for a broad audience of practioners in academia and industry with specializations in such diverse fields as operation research and molecular biology. The work's breadth and the wealth of its scope make it an invaluable resource for specialists, scientists new to the field and for the serious amateur.

Publication Data: Handbook of Discrete and Computational Geometry, 2nd edition, ed. by Jacob E. Goodman and Joseph O'Rourke. Chapman & Hall/CRC, 1539 pages, $139.95. ISBN 1-58488-301-4.