Handbook of discrete and computational geometry. 3rd revised and updated edition. (English) Zbl 1375.52001
Discrete Mathematics and Its Applications. Boca Raton, FL: CRC Press (ISBN 978-1-4987-1139-5/hbk; 978-1-4987-1142-5/ebook). xxi, 1927 p. (2017).
Publisher’s description: This handbook is intended as a reference book fully accessible to nonspecialists as well as specialists, covering all major aspects of both fields.
The book offers the most important results and methods in discrete and computational geometry to those who use them in their work, both in the academic world – as researchers in mathematics and computer science – and in the professional world – as practitioners in fields as diverse as operations research, molecular biology, and robotics.
Discrete geometry has contributed significantly to the growth of discrete mathematics in recent years. This has been fueled partly by the advent of powerful computers and by the recent explosion of activity in the relatively young field of computational geometry. This synthesis between discrete and computational geometry lies at the heart of this Handbook.
A growing list of application fields includes combinatorial optimization, computer-aided design, computer graphics, crystallography, data analysis, error-correcting codes, geographic information systems, motion planning, operations research, pattern recognition, robotics, solid modeling, and tomography.
Features
– Fifty-eight out of the sixty-five chapters have been revised and updated.
– Ten new chapters have been added.
– Five of the new chapters are devoted to computational topology and its applications.
– A new chapter on proximity algorithms gives a comprehensive treatment of relative neighborhood graphs and geometric spanners.
– New chapters on coresets, sketches, e-nets, and e-approximations address geometric methods to cope with large data.
– Two new chapters expand on the recent breakthroughs in rigidity theory.
The articles of this volume will not be indexed individually.
See the reviews of the first and second editions in [Zbl 1056.52001; Zbl 0890.52001].
The book offers the most important results and methods in discrete and computational geometry to those who use them in their work, both in the academic world – as researchers in mathematics and computer science – and in the professional world – as practitioners in fields as diverse as operations research, molecular biology, and robotics.
Discrete geometry has contributed significantly to the growth of discrete mathematics in recent years. This has been fueled partly by the advent of powerful computers and by the recent explosion of activity in the relatively young field of computational geometry. This synthesis between discrete and computational geometry lies at the heart of this Handbook.
A growing list of application fields includes combinatorial optimization, computer-aided design, computer graphics, crystallography, data analysis, error-correcting codes, geographic information systems, motion planning, operations research, pattern recognition, robotics, solid modeling, and tomography.
Features
– Fifty-eight out of the sixty-five chapters have been revised and updated.
– Ten new chapters have been added.
– Five of the new chapters are devoted to computational topology and its applications.
– A new chapter on proximity algorithms gives a comprehensive treatment of relative neighborhood graphs and geometric spanners.
– New chapters on coresets, sketches, e-nets, and e-approximations address geometric methods to cope with large data.
– Two new chapters expand on the recent breakthroughs in rigidity theory.
The articles of this volume will not be indexed individually.
See the reviews of the first and second editions in [Zbl 1056.52001; Zbl 0890.52001].
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 |
Software:
azove; PORTA; Blender; barvinok; WolframAlpha; TOPCOM; Regina; PolyLib; GloptiPoly; cddplus; XPRESS; isl; Tulip; Docker; PPL; GLPK; GTS; QMG; Geometer's Sketchpad; IMAGINARY; simpcomp; COIN-OR; SnapPea; SnapPy; BGL; CirclePack; CindyJS; Matlab; GDToolkit; OpenCL; Triangle; Axel; Hull; Dionysus; javaPlex; Gudhi; Polyominoes; CHomP; Powercrust; GEOMETRICA; Vinci; mplrs; IJK; DGD gallery; Cocone; CompuTop; PHAT; Voronoi; VaryLab; GeoCalcLib; Trelis; Glop; bliss; Detri; VisPak; Minksum; Gfan; Cabri 3D; PCx; Convex; Qhull; lrs; Miniball; SoPlex; Gurobi; nauty; CGAL; SageMath; Graphviz; polymake; CPLEX; Cinderella; MPFR; Mathematica; SCIP; Magma; GeoGebra; Maple; cdd; lpSolve; LEDA; Geomview; jReality; OGDF; gmp; CUDA; Normaliz; Surf; QuickHull3D; LattEOnline Encyclopedia of Integer Sequences:
Number of simplicial arrangements of n lines in the plane (the lines do not pass through a common point, all cells are triangles).Number of primitive sorting networks on n elements; also number of rhombic tilings of a 2n-gon.
Number of projective pseudo order types: simple arrangements of pseudo-lines in the projective plane.
Number of non-isomorphic arrangements of n lines in the real projective plane such that the lines do not all pass through a common point.
Euclidean order types: number of realizable order types of n points in the plane.
Number of nonisomorphic oriented matroids with n points in 2 dimensions.