Newsgroups: comp.graphics.algorithms,sci.math Subject: THE HANDBOOK OF DISCRETE AND COMPUTATIONAL GEOMETRY From: orourke@grendel.csc.smith.edu (Joseph O'Rourke) Date: 8 Nov 97 12:51:32 GMT Keywords: book announcement The following is a reposting of an announcement originally sent out in mid-July. We have learned that some missed it due to summer traveling, etc. Our apologies for the repetition. --------------------------------------------------------------- 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. DESCRIPTION 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. FEATURES o Incorporates complete coverage of both discrete and computational geometry. 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. Includes: o Self-contained definitions: Readers need not consult other works to understand them. 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 Preface v Contributors xi 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 Index 961 [xiv + 991 pages total]