This book covers traditional topics such as convex hulls, triangulations, and Voronoi diagrams, as well as more recent subjects like pseudotriangulations, curve reconstruction, and locked chains. It also touches on more advanced material, including Dehn invariants, associahedra, quasigeodesics, Morse theory, and the recent resolution of the Poincaré conjecture. Connections to real-world applications are made throughout, and algorithms are presented independently of any programming language. This richly illustrated textbook also features numerous exercises and unsolved problems.

The essential introduction to discrete and computational geometry

Covers traditional topics as well as new and advanced material

Features numerous full-color illustrations, exercises, and unsolved problems

Suitable for sophomores in mathematics, computer science, engineering, or physics

Rigorous but accessible

An online solutions manual is available (for teachers only).

1 POLYGONS

1.1 Diagonals and Triangulations

1.2 Basic Combinatorics

1.3 The Art Gallery Theorem

1.4 Scissors Congruence in 2D

1.5 Scissors Congruence in 3D

2 CONVEX HULLS

2.1 Convexity

2.2 The Incremental Algorithm

2.3 Analysis of Algorithms

2.4 Gift Wrapping and Graham Scan

2.5 Lower Bound

2.6 Divide-and-Conquer

2.7 Convex Hull in 3D

3 TRIANGULATIONS

3.1 Basic Constructions

3.2 The Flip Graph

3.3 The Associahedron

3.4 Delaunay Triangulations

3.5 Special Triangulations

4 VORONOI DIAGRAMS

4.1 Voronoi Geometry

4.2 Algorithms to Construct the Diagram

4.3 Duality and the Delaunay Triangulation

4.4 Convex Hull Revisited

5 CURVES

5.1 Medial Axis

5.2 Straight Skeleton

5.3 Minkowski Sums

5.4 Convolution of Curves

5.5 Curve Shortening

5.6 The Heat Equation

5.7 Curve Reconstruction

6 POLYHEDRA

6.1 Platonic Solids

6.2 Euler’s Polyhedral Formula

6.3 The Gauss-Bonnet Theorem

6.4 Cauchy Rigidity

6.5 Shortest Paths

6.6 Geodesics

7 CONFIGURATION SPACES

7.1 Motion Planning

7.2 Polygonal Chains

7.3 Rulers and Locked Chains

7.4 Polygon Spaces

7.5 Particle Collisions

Appendix: Computational Complexity

Permissions

Index