You are here

Handbook of Discrete and Computational Geometry

Jacob E. Goodman and Joseph O'Rourke
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
[Reviewed by
Alex Bogomolny
, on

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.

Alex Bogomolny is a business and educational software developer who lives with his wife and two sons — 26 and 6 — in East Brunswick, NJ. This October, his web site Interactive Mathematics Miscellany and Puzzles has welcomed its 15,0000,000th visitor.

Finite Point Configurations, J. Pach
Packing and Covering, G. Fejes T¢th
Tilings, D. Schattschneider and M. Senechal
Helly-Type Theorems and Geometric Transversals, R. Wenger
Pseudoline Arrangements, J.E. Goodman
Oriented Matroids, J. Richter-Gebert and G.M. Ziegler
Lattice Points and Lattice Polytopes, A. Barvinok
Low-Distortion Embeddings of Finite Metric Spaces, P. Indyk and J. Matousek
New! Geometry and Topology of Polygonal Linkages, R. Connelly and E.D. Demaine
Geometric Graph Theory, J. Pach
Euclidean Ramsey Theory, R.L. Graham
Discrete Aspects of Stochastic Geometry, R. Schneider
Geometric Discrepancy Theory and Uniform Distribution, J.R. Alexander, J. Beck, and W.W.L. Chen
Topological Methods, R.T. Zivaljevic
Polyominoes, S.W. Golomb and D.A. Klarner

Basic Properties of Convex Polytopes, M. Henk, J. Richter-Gebert, and G.M. Ziegler
Subdivisions and Triangulations of Polytopes, C.W. Lee
Face Numbers of Polytopes and Complexes, L.J. Billera and A. Bj”rner
Symmetry of Polytopes and Polyhedra, E. Schulte
Polytope Skeletons and Paths, G. Kalai
Polyhedral Maps, U. Brehm and E. Schulte

Convex Hull Computations, R. Seidel
Voronoi Diagrams and Delaunay Triangulations, S. Fortune
Arrangements, D. Halperin
Triangulations and Mesh Generation, M. Bern
Polygons, J. O'Rourke and S. Suri
Shortest Paths and Networks, J.S.B. Mitchell
Visibility, J. O'Rourke
Geometric Reconstruction Problems, S.S. Skiena
Curve and Surface Reconstruction, T.K. Dey
Computational Convexity, P. Gritzmann and V. Klee
Computational Topology, G. Vegter
Computational Real Algebraic Geometry, B. Mishra

Point Location, J. Snoeyink
Collision and Proximity Queries, M.C. Lin and D. Manocha
Range Searching, P.K. Agarwal
Ray Shooting and Lines in Space, M. Pellegrini
Geometric Intersection, D.M. Mount
Nearest Neighbors in High-Dimensional Spaces, P. Indyk

Randomization and Derandomization, O. Cheong, K. Mulmuley, and E. Ramos
Robust Geometric Computation, C.K. Yap
Parallel Algorithms in Geometry, M.T. Goodrich
Parametric Search, J.S. Salowe
The Discrepancy Method in Computational Geometry, B. Chazelle

Linear Programming, M. Dyer, N. Megiddo, and E. Welzl
Mathematical Programming, M.H. Todd
Algorithmic Motion Planning, M. Sharir
Robotics, D. Halperin, L.E. Kavraki, and J.-C. Latombe
Computer Graphics, D. Dobkin and S. Teller
Modeling Motion, L.J. Guibas
Pattern Recognition, J. O'Rourke and G.T. Toussaint
Graph Drawing, R. Tamassia and G. Liotta
Splines and Geometric Modeling, C.L. Bajaj
Surface Simplification and 3D Geometry Compression, J. Rossignac
Manufacturing Processes, R. Janardan and T.C. Woo
Solid Modeling, C.M. Hoffmann
Computation of Robust Statistics: Depth, Median, and Related Measures, P.J. Rousseeuw and A. Struyf
Geographic Information Systems, M. van Kreveld
Geometric Application of the Grassmann-Cayley Algebra, N.L. White
Rigidity and Scene Analysis, W. Whiteley
Sphere Packing and Coding Theory, G.A. Kabatiansky and J.A. Rush
Crystals and Quasicrystals, M. Senechal
Biological Applications of Computational Topology, H. Edelsbrunner

Software, J. Joswig
Two Computation Geometry Libraries: LEDA and CGAL, L. Kettner and S. N„her

Index of Defined Terms
Index of Cited Authors