The Handbook of Discrete and Computational Geometry 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.

part |380 pages

Combinatorial and Discrete Geometry

chapter 1|23 pages

Finite Point Configurations

ByJános Pach

chapter 2|40 pages

2 Packing and Covering

ByGábor Fejes Tóth

chapter 3|23 pages


ByE. Harriss, D. Schattschneider, M. Senechal

chapter 4|33 pages

Helly-Type Theorems and Geometric Transversals

ByAndreas Holmsen, Rephael Wenger

chapter 5|33 pages

Pseudoline arrangements

ByStefan Felsner, Jacob E. Goodman

chapter 6|26 pages

6: Oriented matroids

ByJürgen Richter-Gebert, Günter M. Ziegler

chapter 7|26 pages

7: Lattice points and lattice polytopes

ByAlexander Barvinok

chapter 8|21 pages

8: Low-distortion embeddings of finite metric spaces

ByPiotr Indyk, Jiří Matoušek, Anastasios Sidiropoulos

chapter 9|24 pages

9: Geometry and topology of polygonal linkages

ByRobert Connelly, Erik D. Demaine

chapter 10|23 pages

10:Geometric graph theory

ByJános Pach

chapter 11|17 pages

Euclidean Ramsey Theory

ByR.L. Graham

chapter 12|31 pages

Discrete Aspects of Stochastic Geometry

ByRolf Schneider

chapter 13|27 pages

Geometric Discrepancy Theory and Uniform Distribution

ByJ. Ralph Alexander, József Beck, William W.L. Chen

chapter 14|22 pages


ByG. Barequet, S.W. Golomb, D.A. Klarner

part |168 pages

Polytopes and Polyhedra

chapter 15|31 pages

Basic Properties of Convex Polytopes

ByMartin Henk, Jürgen Richter-Gebert, Günter M. Ziegler

chapter 16|33 pages

Subdivisions and Triangulations of Polytopes

ByCarl W. Lee, Francisco Santos

chapter 17|27 pages

Face Numbers of Polytopes and Complexes

ByLouis J. Billera, Anders Björner

chapter 18|27 pages

Symmetry of Polytopes and Polyhe Dra

ByEgon Schulte

chapter 19|28 pages

Polytope Skeletons and Paths

ByGil Kalai

chapter 20|16 pages

Polyhedral Maps

ByUlrich Brehm, Egon Schulte

part |135 pages

Combinatorial and Computational Topology

chapter 21|30 pages

Topological Methods in Discrete Geometry

ByRade T. Živaljević

chapter 22|23 pages

Random Simplicial Complexes

ByMatthew Kahle

chapter 23|32 pages

Computational Topology of Graphs on Surfaces

ByÉric Colin de Verdière

chapter 24|25 pages

Persistent Homology

ByHerbert Edelsbrunner, Dmitriy Morozov

chapter 25|21 pages

High-Dimensional Topological Data Analysis

ByFrédéric Chazal

part |318 pages

Algorithms and Complexity of Fundamental Geometric Objects

chapter 26|17 pages

Convex Hull Computations

ByRaimund Seidel

chapter 27|17 pages

Voronoi Diagrams and Delaunay Triangulations

BySteven Fortune

chapter 28|40 pages


ByDan Halperin, Micha Sharir

chapter 29|23 pages

Triangulations and Mesh Generation

ByMarshall Bern, Jonathan R. Shewchuk, Nina Amenta

chapter 30|24 pages


ByJoseph O’Rourke, Subhash Suri, Csaba D. Tóth

chapter 31|38 pages

Shortest Paths and Networks

ByJoseph S.B. Mitchell

chapter 32|26 pages

Proximity Algorithms

ByJoseph S.B. Mitchell

chapter 33|22 pages

Chapter 33: Visibility

ByJoseph O’Rourke

chapter 34|17 pages

Chapter 34: Geometric Reconstruction Problems

ByYann Disser, Steven S. Skiena

chapter 35|22 pages

Chapter 35: Curve and Surface Reconstruction

ByTamal K. Dey

chapter 36|28 pages

Computational Convexity

ByPeter Gritzmann, Victor Klee

chapter 37|34 pages

Computational and quantitative real algebraic geometry

BySaugata Basu, Bhubaneswar Mishra

part |153 pages

Geometric data Structures and Searching

chapter 38|24 pages

Point Location

ByJack Snoeyink

chapter 39|28 pages

Collision and Proximity Queries

ByMing C. Lin, Dinesh Manocha, Young J. Kim

chapter 40|36 pages

Range Searching

ByPankaj K. Agarwal

chapter 41|20 pages

Ray shooting and lines in space

ByMarco Pellegrini

chapter 42|22 pages

Geometric intersection

ByDavid M. Mount

chapter 43|21 pages

Nearest neighbors in high-dimensional spaces

ByAlexandr Andoni, Piotr Indyk

part |132 pages

Computational Techniques

chapter 44|29 pages

Randomization and Derandomization

ByOtfried Cheong, Ketan Mulmuley, Edgar Ramos

chapter 45|35 pages

Robust geometric computation

ByVikram Sharma, Chee K. Yap

chapter 46|15 pages

Parallel Algorithms In Geometry

ByMichael T. Goodrich, Nodari Sitchinava

chapter 47|27 pages

Epsilon-Approximations & Epsilon-Nets

ByNabil H. Mustafa, Kasturi Varadarajan

chapter 48|20 pages

Coresets and Sketches

ByJeff M. Phillips

part |487 pages

Applications of Discrete and Computational Geometry

chapter 49|19 pages

Linear Programming

ByMartin Dyer, Bernd Gärtner, Nimrod Megiddo, Emo Welzl

chapter 50|32 pages

Algorithmic Motion Planning

ByDan Halperin, Oren Salzman, Micha Sharir

chapter 51|34 pages


ByDan Halperin, Lydia E. Kavraki, Kiril Solovey

chapter 52|23 pages

Computer Graphics

ByDavid Dobkin, Seth Teller

chapter 53|20 pages

Modeling motion

ByLeonidas J Guibas, Marcel Roeloffzen

chapter 54|30 pages

Pattern recognition

ByJoseph O’Rourke, G.T. Toussaint

chapter 55|27 pages

Graph Drawing

ByEmilio Di Giacomo, Giuseppe Liotte, Roberto Tamassia

chapter 56|24 pages

Splines and geometric modeling

ByChandrjit L. Bajaj

chapter 57|37 pages

Solid modeling

ByChristoph M. Hoffmann, Vadim Shapiro

chapter 58|14 pages

Computation of Robust Statistics: Depth, Median, and Related Measures

ByPeter J. Rousseeuw, M. Hubert

chapter 59|26 pages

Geographic Information Systems

ByM. van Kreveld

chapter 60|12 pages

Geometric Applications of the Grassmann-Cayley Algebra

ByN.L. White

chapter 61|40 pages

Rigidity and Scene Analysis

ByBernd Schulze, Walter Whiteley

chapter 62|27 pages

Rigidity of Symmetric Frameworks

ByBernd Schulze, Walter Whiteley

chapter 63|34 pages

Global Rigidity

ByTibor Jordán, Walter Whiteley

chapter 64|14 pages

Crystals, Periodic and Aperiodic

ByMarjorie Senechal

chapter 65|27 pages

Computational Topology for Structural Molecular Biology

ByHerbert Edelsbrunner, Patrice Koehl

chapter 66|39 pages

Geometry and Topology of Genomic Data

ByAndrew J. Blumberg, Raúl Rabadán

part |55 pages

Geometric Software

chapter 67|20 pages


ByMichael Joswig, Benjamin Lorenz

chapter 68|33 pages

Two Computational Geometry Libraries: LEDA and CGAL

ByMichael Hoffmann, Lutz Kettner, Stefan Näher