Book Announcement: Handbook of Discrete & Computational Geometry

Book Announcement: Handbook of Discrete & Computational Geometry

Post by Joseph O'Rour » Thu, 17 Jul 1997 04:00:00



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]

 
 
 

Book Announcement: Handbook of Discrete & Computational Geometry

Post by Joseph O'Rour » Thu, 17 Jul 1997 04:00:00


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]

 
 
 

Book Announcement: Handbook of Discrete & Computational Geometry

Post by Joseph O'Rour » Mon, 28 Jul 1997 04:00:00




>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.).

A note for the graphics community: CRC Press will have a booth at
SIGGRAPH, and will have copies of the Handbook available for
examination and for purchase.