Handbook of Discrete and Computational Geometry, Second Edition

Series:
Discrete Mathematics and Its Applications
Published:
April 13, 2004 by Chapman and Hall/CRC - 1,560 Pages
Editor(s):
Jacob E. Goodman, City College, New York, New York, USA; Joseph O'Rourke, Smith College, Northampton, Massachusetts, USA

Purchasing Options

Hardback
$159.95
Add to cart
ISBN 9781584883012
Cat# C3014
 

Features

  • Provides a one-stop reference both for researchers in geometry and geometric computing and for professionals who use geometric tools in their work
  • Covers a broad range of topics in discrete and computational geometry as well as numerous applications
  • Presents results in the forms of theorems, algorithms, and tables
  • Addresses many important new developments in the field, including solution of the Kepler conjecture, results on the 2-center problem, new bounds on k-sets and geometric permutations, and new art gallery theorems
  • Includes nearly 300 illustrations, almost 200 tables, and glossaries that provide clear definitions of more than 4000 terms

    • Summary

    While high-quality books and journals in this field continue to proliferate, none has yet come close to matching the Handbook of Discrete and Computational Geometry, which in its first edition, quickly became the definitive reference work in its field. But with the rapid growth of the discipline and the many advances made over the past seven years, it's time to bring this standard-setting reference up to date.

    Editors Jacob E. Goodman and Joseph O'Rourke reassembled their stellar panel of contributors, added manymore, and together thoroughly revised their work to make the most important results and methods, both classic and cutting-edge, accessible in one convenient volume. Now over more then 1500 pages, the Handbook of Discrete and Computational Geometry, Second Edition once again provides unparalleled, authoritative coverage of theory, methods, and applications.

    Highlights of the Second Edition:

  • Thirteen new chapters: Five on applications and others on collision detection, nearest neighbors in high-dimensional spaces, curve and surface reconstruction, embeddings of finite metric spaces, polygonal linkages, the discrepancy method, and geometric graph theory
  • Thorough revisions of all remaining chapters
  • Extended coverage of computational geometry software, now comprising two chapters: one on the LEDA and CGAL libraries, the other on additional software
  • Two indices: An Index of Defined Terms and an Index of Cited Authors
  • Greatly expanded bibliographies

    • Table of Contents

    COMBINATORIAL AND DISCRETE GEOMETRY
    Finite Point Configurations, J. Pach
    Packing and Covering, G. Fejes Tóth
    Tilings, D. Schattschneider and M. Senechal
    Helly-Type Theorems and Geometric Transversals, R. Wenger
    Pseudoline Arrangements, J.E. Goodman
    Oriented Matroids, J. Richter-Gebert and G.M. Ziegler
    Lattice Points and Lattice Polytopes, A. Barvinok
    New! Low-Distortion Embeddings of Finite Metric Spaces, P. Indyk and J. Matousek
    New! Geometry and Topology of Polygonal Linkages, R. Connelly and E.D. Demaine
    New! Geometric Graph Theory, J. Pach
    Euclidean Ramsey Theory, R.L. Graham
    Discrete Aspects of Stochastic Geometry, R. Schneider
    Geometric Discrepancy Theory and Uniform Distribution, J.R. Alexander, J. Beck, and W.W.L. Chen
    Topological Methods, R.T. Zivaljevic
    Polyominoes, S.W. Golomb and D.A. Klarner

    POLYTOPES AND POLYHEDRA
    Basic Properties of Convex Polytopes, M. Henk, J. Richter-Gebert, and G.M. Ziegler
    Subdivisions and Triangulations of Polytopes, C.W. Lee
    Face Numbers of Polytopes and Complexes, L.J. Billera and A. Björner
    Symmetry of Polytopes and Polyhedra, E. Schulte
    Polytope Skeletons and Paths, G. Kalai
    Polyhedral Maps, U. Brehm and E. Schulte

    ALGORITHMS AND COMPLEXITY OF FUNDAMENTAL GEOMETRIC OBJECTS
    Convex Hull Computations, R. Seidel
    Voronoi Diagrams and Delaunay Triangulations, S. Fortune
    Arrangements, D. Halperin
    Triangulations and Mesh Generation, M. Bern
    Polygons, J. O'Rourke and S. Suri
    Shortest Paths and Networks, J.S.B. Mitchell
    Visibility, J. O'Rourke
    Geometric Reconstruction Problems, S.S. Skiena
    New! Curve and Surface Reconstruction, T.K. Dey
    Computational Convexity, P. Gritzmann and V. Klee
    Computational Topology, G. Vegter
    Computational Real Algebraic Geometry, B. Mishra

    GEOMETRIC DATA STRUCTURES AND SEARCHING
    Point Location, J. Snoeyink
    New! Collision and Proximity Queries, M.C. Lin and D. Manocha
    Range Searching, P.K. Agarwal
    Ray Shooting and Lines in Space, M. Pellegrini
    Geometric Intersection, D.M. Mount
    New! Nearest Neighbors in High-Dimensional Spaces, P. Indyk

    COMPUTATIONAL TECHNIQUES
    Randomization and Derandomization, O. Cheong, K. Mulmuley, and E. Ramos
    Robust Geometric Computation, C.K. Yap
    Parallel Algorithms in Geometry, M.T. Goodrich
    Parametric Search, J.S. Salowe
    New! The Discrepancy Method in Computational Geometry, B. Chazelle

    APPLICATIONS OF DISCRETE AND COMPUTATIONAL GEOMETRY
    Linear Programming, M. Dyer, N. Megiddo, and E. Welzl
    Mathematical Programming, M.H. Todd
    Algorithmic Motion Planning, M. Sharir
    Robotics, D. Halperin, L.E. Kavraki, and J.-C. Latombe
    Computer Graphics, D. Dobkin and S. Teller
    New! Modeling Motion, L.J. Guibas
    Pattern Recognition, J. O'Rourke and G.T. Toussaint
    Graph Drawing, R. Tamassia and G. Liotta
    Splines and Geometric Modeling, C.L. Bajaj
    New! Surface Simplification and 3D Geometry Compression, J. Rossignac
    Manufacturing Processes, R. Janardan and T.C. Woo
    Solid Modeling, C.M. Hoffmann
    New! Computation of Robust Statistics: Depth, Median, and Related Measures, P.J. Rousseeuw and A. Struyf
    New! Geographic Information Systems, M. van Kreveld
    Geometric Application of the Grassmann-Cayley Algebra, N.L. White
    Rigidity and Scene Analysis, W. Whiteley
    Sphere Packing and Coding Theory, G.A. Kabatiansky and J.A. Rush
    Crystals and Quasicrystals, M. Senechal
    New! Biological Applications of Computational Topology, H. Edelsbrunner

    New! GEOMETRIC SOFTWARE
    Software, J. Joswig
    Two Computation Geometry Libraries: LEDA and CGAL, L. Kettner and S. Näher

    Index of Defined Terms
    New! Index of Cited Authors

    Editorial Reviews

    "[T]his book puts together under one cover more and broader information on discrete (= combinatorial) and computational geometry than any other book in existence. Better yet, chapters of the book have been written by some of the best informed in their subject matter …[A]ctive mathematicians and scientists in many … fields - such as computer science, physics, biology, chemistry, etc. - will browse this volume profitably in search for tools that can aid them in their creative endeavors. This is the second edition … . It is therefore fair to ask, should those who [bought] the first edition buy this edition as well? I think so, for it offers 500 additional pages, thoroughly revised old chapters, and 14 new chapters."
    - Geombinatorics XIV(3), January 2005

    "The second edition of this remarkable handbook is 50% larger than the first…clearly written and well-organized..this handbook should be available in research and academic libraries as well as mathematics department libraries."
    E-Streams, 2005

    "This laptop of a handbook is a tremendous collection of 65 articles on discrete and computational geometry. The organization of this book is superb. The work's breadth and the wealth of its scope make in an invaluable resource…"
    laptop of a handbook is a tremendous collection of 65 articles on discrete and computational geometry. The organization of this book is superb. The work's breadth and the wealth of its scope make in an invaluable resource…"

    Related Titles