Handbook of Discrete and Computational Geometry

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