Discrete and Computational Geometry bridges the theoretical world of discrete geometry with the applications-driven realm of computational geometry, offering a comprehensive yet accessible introduction to this cutting-edge frontier of mathematics and computer science. Beginning with polygons and ending with polyhedra, it explains how to capture the shape of data given by a set of points, from convex hulls and triangulations to Voronoi diagrams, geometric duality, chains, linkages, and alpha complexes. Connections to real-world applications are made throughout, and algorithms are presented independent of any programming language. Now fully updated and expanded, this richly illustrated textbook is an invaluable learning tool for students in mathematics, computer science, engineering, and physics.
- Now with new sections on duality and on computational topology
- Project suggestions at the end of every chapter
- Covers traditional topics as well as new and advanced material
- Features numerous full-color illustrations, exercises, and fully updated unsolved problems
- Uniquely designed for a one-semester class
- Accessible to college sophomores with minimal background
- Also suitable for more advanced students
- Online solutions manual (available to instructors)
Satyan L. Devadoss is the Fletcher Jones Professor of Applied Mathematics and Professor of Computer Science at the University of San Diego. He is the author (with Matthew Harvey) of Mage Merlin’s Unsolved Mathematical Mysteries. He is a Fellow of the American Mathematical Society and recipient of two national teaching awards from the Mathematical Association of America. Joseph O’Rourke is the Olin Professor of Computer Science and Professor of Mathematics (Emeritus) at Smith College. His books include How to Fold It: The Mathematics of Linkages, Origami, and Polyhedra. He was the chair of the first Symposium on Computational Geometry, the premier conference in the field.
- Preface to the First Edition
- Preface to the Second Edition
- 1 Polygons
- 1.1 The Jordan Curve Theorem
- 1.2 Diagonals and Triangulations
- 1.3 Polygon Combinatorics
- 1.4 The Art Gallery Theorem
- 1.5 Scissors Congruence in 2D
- 1.6 Scissors Congruence in 3D
- 2 Convex Hulls
- 2.1 Convexity
- 2.2 Incremental Construction
- 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 Algorithms and Combinatorics
- 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 Combinatorics and Algorithms
- 4.3 Revisiting the Delaunay Triangulation
- 4.4 Revisiting the Convex Hull
- 4.5 Geometric Duality
- 5 Shape Recovery
- 5.1 Medial Axis
- 5.2 Straight Skeleton
- 5.3 Curve Reconstruction
- 5.4 Disks and Deformations
- 5.5 The Alpha Complex
- 5.6 Alpha Complex Construction
- 6 Polygonal Chains
- 6.1 Cauchy鈥檚 Arm Lemma
- 6.2 Chain Con铿乬urations
- 6.3 Folding Chains and Reaching Chains
- 6.4 Straightening Chains in 2D and 3D
- 6.5 Shortening Chains
- 7 Polyhedra
- 7.1 Platonic Solids
- 7.2 Euler鈥檚 Polyhedral Formula
- 7.3 The Gauss-Bonnet Theorem
- 7.4 Cauchy鈥檚 Rigidity Theorem
- 7.5 D眉rer鈥檚 Unfolding Problem
- 7.6 Shortest Paths
- 7.7 Star Unfolding and Source Unfolding
- 7.8 Alexandrov鈥檚 Gluing Theorem
- Appendix: Computational Complexity
- Index
“[Discrete and Computational Geometry] meets an urgent need for an undergraduate text bridging the theoretical sides and the applied sides of the field. It is an excellent choice as a textbook for an undergraduate course in discrete and computational geometry! The presented material should be accessible for most mathematics or computer science majors in their second or third year in college. The book also is a valuable resource for graduate students and researchers.”—Egon Schulte, Zentralblatt MATH
“We recommend this book for an undergraduate course on computational geometry. In fact, we hope to use this book ourselves when we teach such a class.”—Brittany Terese Fasy and David L. Millman, SIGACT News
