THE HANDBOOK OF DISCRETE AND COMPUTATIONAL GEOMETRY
J. E. Goodman and J. O'Rourke, editors.
CRC Press LLC, Boca Raton, FL; published July, 1997.
52 chapters, xiv + 991 pages; ISBN:0-8493-8524-5. $99.95.
Follow links from http://cs.smith.edu/~orourke/ for ordering information,
or call CRC: 1-800-272-7737 (U.S.); 1-561-994-0555 (outside U.S.).
Advisory Editorial Board:
D.P. Dobkin, H. Edelsbrunner, R.L. Graham, B. Grunbaum, V. Klee,
D.E. Knuth, R. Pollack, F.P. Preparata, G.-C. Rota.
Over the past decade or so, researchers and professionals in
discrete geometry and the newer field of computational geometry have
developed a highly productive collaborative relationship, where each
area benefits from the methods and insights of the other. At the same time
that discrete and computational geometry are becoming more closely
identified, applications of the results of this work are being used in
an increasing number of widely differing areas, from computer graphics
and linear programming to manufacturing and robotics. The authors have
answered the need for a comprehensive handbook for workers in these and
related fields, and for other users of the body of results.
While much information can be found on discrete and computational
geometry, it is scattered among many sources, and individual books and
articles are often narrowly focused. The Handbook of Discrete and
Computational Geometry brings together, for the first time, all of the
major results in both these fields into one volume. Thousands of results,
theorems, algorithms, and tables throughout the volume definitively cover
the field, while numerous applications from many different fields demonstrate
practical usage. The material is presented clearly enough to assist the
novice, but in enough depth to appeal to the specialist. Every technical
term is clearly defined in an easy-to-use glossary. Over 200 figures
illustrate the concepts presented and provide supporting examples.
Information on current geometric software, what it does, how efficiently
it does it, and where to find it is also included.
o Incorporates complete coverage of both discrete and computational
o Includes numerous applications.
o Each chapter is authoritative, written by one of the world's
leading experts in the area.
o Clearly presented and comprehensive, to make the information accessible
to both the novice and the specialist.
o Designed to assist both researchers in geometry and professionals who use
geometric tools in the workplace.
o Self-contained definitions: Readers need not consult other works to
o Theorems: Stated in lucid language.
o Algorithms: What each one does, as well as its time and space complexity.
o Tables: Results systematized into over 150 tables.
o Open problems: Isolated and formulated by the leading authorities.
o Examples: Illustrate the main results for specific cases.
o Glossaries: Key terminology used throughout the volume, complete
with short definitions of over 2000 terms.
o Software compilation: A final chapter lists both commercial and public
domain computational geometry software, including Internet and Web sources.
TABLE OF CONTENTS
COMBINATORIAL AND DISCRETE GEOMETRY 1
1 Finite point configurations (J. Pach) 3
2 Packing and covering (G. Fejes Toth) 19
3 Tilings (D. Schattschneider and M. Senechal) 43
4 Helly-type theorems and geometric transversals (R. Wenger) 63
5 Pseudoline arrangements (J.E. Goodman) 83
6 Oriented matroids (J. Richter-Gebert and G.M. Ziegler) 111
7 Lattice points and lattice polytopes (A. Barvinok) 133
8 Euclidean Ramsey theory (R.L. Graham) 153
9 Discrete aspects of stochastic geometry (R. Schneider) 167
10 Geometric discrepancy theory and uniform distribution
(J.R. Alexander, J. Beck, and W.W.L. Chen) 185
11 Topological methods (R.T. Zivaljevic) 209
12 Polyominoes (D.A. Klarner) 225
POLYTOPES AND POLYHEDRA 241
13 Basic properties of convex polytopes
(M. Henk, J. Richter-Gebert, and G.M. Ziegler) 243
14 Subdivisions and triangulations of polytopes (C.W. Lee) 271
15 Face numbers of polytopes and complexes
(L.J. Billera and A. Bj"orner) 291
16 Symmetry of polytopes and polyhedra (E. Schulte) 311
17 Polytope skeletons and paths (G. Kalai) 331
18 Polyhedral maps (U. Brehm and E. Schulte) 345
ALGORITHMS AND COMPLEXITY OF FUNDAMENTAL GEOMETRIC OBJECTS 359
19 Convex hull computations (R. Seidel) 361
20 Voronoi diagrams and Delaunay triangulations (S. Fortune) 377
21 Arrangements (D. Halperin) 389
22 Triangulations (M. Bern) 413
23 Polygons (S. Suri) 429
24 Shortest paths and networks (J. Mitchell) 445
25 Visibility (J. O'Rourke) 467
26 Geometric reconstruction problems (S.S. Skiena) 481
27 Computational convexity (P. Gritzmann and V. Klee) 491
28 Computational topology (G. Vegter) 517
29 Computational real algebraic geometry (B. Mishra) 537
GEOMETRIC DATA STRUCTURES AND SEARCHING 557
30 Point location (J. Snoeyink) 559
31 Range searching (P. Agarwal) 575
32 Ray shooting and lines in space (M. Pellegrini) 599
33 Geometric intersection (D. Mount) 615
COMPUTATIONAL TECHNIQUES 631
34 Randomized algorithms (K. Mulmuley and O. Schwarzkopf) 633
35 Robust geometric computation (C.K. Yap) 653
36 Parallel algorithms in geometry (M.T. Goodrich) 669
37 Parametric search (J. Salowe) 683
APPLICATIONS OF DISCRETE AND COMPUTATIONAL GEOMETRY 697
38 Linear programming in low dimensions (M. Dyer and N. Megiddo) 699
39 Mathematical programming (M.J. Todd) 711
40 Algorithmic motion planning (M. Sharir) 733
41 Robotics (D. Halperin, L. Kavraki, and J.-C. Latombe) 755
42 Computer graphics (D. Dobkin and S. Teller) 779
43 Pattern recognition (J. O'Rourke and G.T. Toussaint) 797
44 Graph drawing (R. Tamassia) 815
45 Splines and geometric modeling (C.L. Bajaj and S. Evans) 833
46 Manufacturing processes (R. Janardan and T. Woo) 851
47 Solid modeling (C.M. Hoffmann) 863
48 Geometric applications of the Grassmann-Cayley algebra
(N.L. White) 881
49 Rigidity and scene analysis (W. Whiteley) 893
50 Sphere packing and coding theory (J.A. Rush) 917
51 Crystals and quasicrystals (M. Senechal) 933
52 Computational geometry software (N. Amenta) 951
[xiv + 991 pages total]