- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Chapman & Hall/CRC

Publication Date:

2004

Number of Pages:

1539

Format:

Hardcover

Edition:

2

Price:

139.95

ISBN:

1584883014

Category:

Handbook

[Reviewed by , on ]

Alex Bogomolny

12/28/2005

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,000^{th} visitor.

COMBINATORIAL AND DISCRETE GEOMETRY

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

POLYTOPES AND POLYHEDRA

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

ALGORITHMS AND COMPLEXITY OF FUNDAMENTAL GEOMETRIC OBJECTS

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

GEOMETRIC DATA STRUCTURES AND SEARCHING

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

COMPUTATIONAL TECHNIQUES

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

APPLICATIONS OF DISCRETE AND COMPUTATIONAL GEOMETRY

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

GEOMETRIC SOFTWARE

Software, J. Joswig

Two Computation Geometry Libraries: LEDA and CGAL, L. Kettner and S. Nâ€žher

Index of Defined Terms

Index of Cited Authors

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

POLYTOPES AND POLYHEDRA

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

ALGORITHMS AND COMPLEXITY OF FUNDAMENTAL GEOMETRIC OBJECTS

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

GEOMETRIC DATA STRUCTURES AND SEARCHING

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

COMPUTATIONAL TECHNIQUES

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

APPLICATIONS OF DISCRETE AND COMPUTATIONAL GEOMETRY

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

GEOMETRIC SOFTWARE

Software, J. Joswig

Two Computation Geometry Libraries: LEDA and CGAL, L. Kettner and S. Nâ€žher

Index of Defined Terms

Index of Cited Authors

- Log in to post comments