Handbook of discrete and computational geometry.

*(English)*Zbl 0890.52001
CRC Press Series on Discrete Mathematics and its Applications. Boca Raton, FL: CRC Press. xvi, 991 p. (1997).

**
Show indexed articles as search result.
**

From the preface: “The Handbook of Discrete and Computational Geometry is intended to make the most important results and methods in the areas of discrete and computational geometry readily accessible to those who use them in their everyday work, both in the academic world – as researchers in mathematics and computer science – and in the professional world – as practitioners in field as diverse as operations research, molecular biology, and robotics.

The phrase “discrete geometry,” which at one time stood mainly for the areas of packing, covering, and tiling, has gradually grown to include in addition such areas as combinatorial geometry, convex polytopes, and arrangements of points, lines, planes, circles, and other geometric objects in the plane and in higher dimensions. Similarly, “computational geometry,” nowadays means the study of geometric problems from a computational point of view, including also computational convexity, computational topology, and questions involving the combinatorial complexity of arrangements and polyhedra.

Areas of applications of the results of this work are engineering, crystallography, computer-aided design, manufacturing, operations research, geographic information systems, robotics, error-correcting codes, tomography, geometric modeling, computer graphics, combinatorial optimization, computer vision, pattern recognition, and solid modeling.

Results are presented in the form of theorems, algorithms, and tables, with every technical term carefully defined in a glossary that precedes the section in which the turn is first used. There are numerous examples and figures to illustrate the ideas discussed, as well as a large number of unsolved problems.”

The main body of the volume is divided into six parts. See the following table of contents with explicit titles and authors of the contributions.

Combinatorial and discrete geometry

1. Finite point configurations by J. Pach; 2. Packing and covering by G. Fejes Tóth; 3. Tilings by D. Schattschneider and M. Senechal; 4. Helly-type theorems and geometric transversals by R. Wenger; 5. Pseudoline arrangements by J. E. Goodman; 6. Oriented matroids by J. Richter-Gebert and G. M. Ziegler; 7. Lattice points and lattice polytopes by A. Barvinok; 8. Euclidean Ramsey theory by R. L. Graham; 9. Discrete aspects of stochastic geometry by R. Schneider; 10. Geometric discrepancy theory and uniform distribution by J. R. Alexander, J. Beck and W. W. L. Chen; 11. Topological methods by R. T. Živaljević; 12. Polyominoes by D. A. Klarner.

Polytopes and polyhedra

13. Basic properties of convex polytopes by M. Henk, J. Richter-Gebert and G. M. Ziegler; 14. Subdivisions and triangulations of polytopes by C. W. Lee; 15. Face numbers of polytopes and complexes by L. J. Billera and A. Björner; 16. Symmetry of polytopes and polyhedra by E. Schulte; 17. Polytope skeletons and paths by G. Kalai; 18. Polyhedral maps by U. Brehm and E. Schulte.

Algorithms and complexity of fundamental geometric objects

19. Convex hull computations by R. Seidel; 20. Voronoi diagrams and Delaunay triangulations by S. Fortune; 21. Arrangements by D. Halperin; 22. Triangulations by M. Bern; 23. Polygons by S. Suri; 24. Shortest paths and networks by J. Mitchell; 25. Visibility by J. O’Rourke; 26. Geometric reconstruction problems by S. S. Skiena; 27. Computational convexity by P. Gritzmann and V. Klee; 28. Computational topology by G. Vegter; 29. Computational real algebraic geometry by B. Mishra.

Geometric data structures and searching

30. Point location by J. Snoeyink; 31. Range searching by P. Agarwal; 32. Ray shooting and lines in space by M. Pellegrini; 33. Geometric intersection by D. Mount.

Computational techniques

34. Randomized algorithms by K. Mulmuley and O. Schwarzkopf; 35. Robust geometric computation by C. K. Yap; 36. Parallel algorithms in geometry by M. T. Goodrich; 37. Parametric search by J. Salowe.

Applications of discrete and computational geometry;

38. Linear programming in low dimensions by M. Dyer and N. Megiddo; 39. Mathematical programming by M. J. Todd; 40. Algorithmic motion planning by M. Sharir; 41. Robotics by D. Halperin, L. Kavraki and J.-C. Latombe; 42. Computer graphics by D. Dobkin and S. Teller; 43. Pattern recognition by J. O’Rourke and G. T. Toussaint; 44. Graph drawing by R. Tamassia; 45. Splines and geometric modeling by C. L. Bajaj and S. Evans; 46. Manufacturing processes by R. Janardan and T. Woo; 47. Solid modeling by C. M. Hoffmann; 48. Geometric applications of the Grassmann-Cayley algebra by N. L. White; 49. Rigidity and scene analysis by W. Whiteley; 50. Sphere packing and coding theory by J. A. Rush; 51. Crystals and quasicrystals by M. Senechal; 52. Computational geometry software by N. Amenta.

Indexed articles:

Pach, János, Finite point configurations, 3-18 [Zbl 0914.51012]

Fejes Tóth, Gábor, Packing and covering, 19-41 [Zbl 0924.52007]

Schattschneider, Doris; Senechal, Marjorie, Tilings, 43-62 [Zbl 0911.52013]

Wenger, Rephael, Helly-type theorems and geometric transversals, 63-82 [Zbl 0912.52006]

Goodman, Jacob E., Pseudoline arrangements, 83-109 [Zbl 0914.51007]

Richter-Gebert, Jürgen; Ziegler, Günter M., Oriented matroids, 111-132 [Zbl 0902.05015]

Barvinok, Alexander, Lattice points and lattice polytopes, 133-152 [Zbl 0912.52009]

Graham, R. L., Euclidean Ramsey theory, 153-166 [Zbl 0902.05073]

Schneider, Rolf, Discrete aspects of stochastic geometry, 167-184 [Zbl 0907.60019]

Alexander, J. Ralph; Beck, József; Chen, William W. L., Geometric discrepancy theory and uniform distribution, 185-207 [Zbl 1027.11504]

Živaljević, Rade T., Topological methods, 209-224 [Zbl 0955.52500]

Klarner, David A., Polyominoes, 225-240 [Zbl 0901.05031]

Henk, Martin; Richter-Gebert, Jürgen; Ziegler, Günter M., Basic properties of convex polytopes, 243-270 [Zbl 0911.52007]

Lee, Carl W., Subdivisions and triangulations of polytopes, 271-290 [Zbl 0917.52012]

Billera, Louis J.; Björner, Anders, Face numbers of polytopes and complexes, 291-310 [Zbl 0917.52008]

Schulte, Egon, Symmetry of polytopes and polyhedra, 311-330 [Zbl 0916.52004]

Kalai, Gil, Polytope skeletons and paths, 331-344 [Zbl 0910.52005]

Brehm, Ulrich; Schulte, Egon, Polyhedral maps, 345-358 [Zbl 0920.52004]

Seidel, Raimund, Convex hull computations, 361-375 [Zbl 0907.68189]

Fortune, Steven, Voronoi diagrams and Delaunay triangulations, 377-388 [Zbl 0907.68190]

Halperin, Dan, Arrangements, 389-412 [Zbl 0907.68191]

Bern, Marshall, Triangulations, 413-428 [Zbl 0907.68192]

Suri, Subhash, Polygons, 429-444 [Zbl 0907.68193]

Mitchell, Joseph S. B., Shortest paths and networks, 445-466 [Zbl 0907.68194]

O’Rourke, Joseph, Visibility, 467-479 [Zbl 0907.68195]

Skiena, Steven S., Geometric reconstruction problems, 481-490 [Zbl 0916.51001]

Gritzmann, Peter; Klee, Victor, Computational convexity, 491-515 [Zbl 1023.52004]

Vegter, Gert, Computational topology, 517-536 [Zbl 0955.65502]

Mishra, Bhubaneswar, Computational real algebraic geometry, 537-556 [Zbl 0940.68184]

Snoeyink, Jack, Point location, 559-574 [Zbl 0907.68196]

Agarwal, Pankaj K., Range searching, 575-598 [Zbl 0907.68197]

Pellegrini, Marco, Ray shooting and lines in space, 599-614 [Zbl 0907.68198]

Mount, David M., Geometric intersection, 615-630 [Zbl 0907.68199]

Mulmuley, Ketan; Schwarzkopf, Otfried, Randomized algorithms, 633-652 [Zbl 0907.68115]

Yap, Chee K., Robust geometric computation, 653-668 [Zbl 0907.68091]

Goodrich, Michael T., Parallel algorithms in geometry, 669-681 [Zbl 0907.68106]

Salowe, Jeffrey S., Parametric search, 683-695 [Zbl 0907.68058]

Dyer, Martin; Megiddo, Nimrod, Linear programming in low dimensions, 699-710 [Zbl 0904.90115]

Todd, Michael J., Mathematical programming, 711-731 [Zbl 0904.90155]

Sharir, Micha, Algorithmic motion planning, 733-754 [Zbl 0925.93625]

Halperin, Dan; Kavraki, Lydia; Latombe, Jean-Claude, Robotics, 755-778 [Zbl 0925.93626]

Dobkin, David; Teller, Seth, Computer graphics, 779-795 [Zbl 0907.68200]

O’Rourke, Joseph; Toussaint, Godfried T., Pattern recognition, 797-813 [Zbl 0907.68174]

Tamassia, Roberto, Graph drawing, 815-832 [Zbl 0905.05075]

Bajaj, Chandrajit L.; Evans, Susan, Splines and geometric modeling, 833-849 [Zbl 0902.65004]

Janardan, Ravi; Woo, Tony C., Design and manufacturing, 851-862 [Zbl 0907.68202]

Hoffmann, Christoph M., Solid modeling, 863-880 [Zbl 0907.68203]

White, Neil L., Geometric applications of the Grassmann-Cayley algebra, 881-892 [Zbl 0902.15024]

Whiteley, Walter, Rigidity and scene analysis, 893-916 [Zbl 0902.52008]

Rush, J. A., Sphere packing and coding theory, 917-932 [Zbl 0910.52016]

Senechal, Marjorie, Crystals and quasicrystals, 933-949 [Zbl 0910.51006]

Amenta, Nina, Computational geometry software, 951-960 [Zbl 0907.68201]

##### MSC:

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |

51Exx | Finite geometry and special incidence structures |

65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |

68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |

05B35 | Combinatorial aspects of matroids and geometric lattices |

11-02 | Research exposition (monographs, survey articles) pertaining to number theory |

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |