Discrete and Computational Geometry
Год издания: 2011
Автор: Satyan L. Devadoss & Joseph O'Rourke
Жанр или тематика: Discrete and Computational Geometry
Издательство: Princeton University Press
ISBN: 978-0-691-14553-2
Язык: Английский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 270
Описание: applications-driven computer science. Their intermingling has yielded exciting advances in recent years, yet what has been lacking until now is an undergraduate textbook that bridges the gap between the two. Discrete and Computational Geometry offers a comprehensive yet accessible introduction to this cutting-edge frontier of mathematics and computer science.
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.
Оглавление
1 POLYGONS
1.1 Diagonals and Triangulations 1
1.2 Basic Combinatorics 7
1.3 The Art Gallery Theorem 13
1.4 Scissors Congruence in 2D 20
1.5 Scissors Congruence in 3D 26
2 CONVEX HULLS
2.1 Convexity 33
2.2 The Incremental Algorithm 36
2.3 Analysis of Algorithms 39
2.4 Gift Wrapping and Graham Scan 42
2.5 Lower Bound 46
2.6 Divide-and-Conquer 48
2.7 Convex Hull in 3D 51
3 TRIANGULATIONS
3.1 Basic Constructions 59
3.2 The Flip Graph 66
3.3 The Associahedron 73
3.4 Delaunay Triangulations 79
3.5 Special Triangulations 87
4 VORONOI DIAGRAMS
4.1 Voronoi Geometry 98
4.2 Algorithms to Construct the Diagram 104
4.3 Duality and the Delaunay Triangulation 107
4.4 Convex Hull Revisited 113
5 CURVES
5.1 Medial Axis 118
5.2 Straight Skeleton 125
5.3 Minkowski Sums 128
5.4 Convolution of Curves 132
5.5 Curve Shortening 138
5.6 The Heat Equation 144
5.7 Curve Reconstruction 148
6 POLYHEDRA
6.1 Platonic Solids 156
6.2 Euler’s Polyhedral Formula 162
6.3 The Gauss-Bonnet Theorem 170
6.4 Cauchy Rigidity 177
6.5 Shortest Paths 188
6.6 Geodesics 200
7 CONFIGURATION SPACES
7.1 Motion Planning 206
7.2 Polygonal Chains 215
7.3 Rulers and Locked Chains 221
7.4 Polygon Spaces 229
7.5 Particle Collisions 237
Appendix: Computational Complexity 245
Permissions 249
Index 251
Доп. информация: Reviews:
"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
"[W]e 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
Endorsements:
"This book is ideal for people who want to learn about the topic without wading too deeply into technical details. I really like the figures, and the writing style is very nice for students, with frequent jumps into exercises. The book favors topics that are intuitive, engaging, and easily grasped. It could form the basis of an excellent undergraduate-level course for students in computer science, applied mathematics, and pure mathematics."--Samir Khuller, University of Maryland
"I thoroughly enjoyed reading this book. It covers an incredibly diverse set of topics, ranging from elementary objects to deep mathematical concepts and important computational problems. Devadoss and O'Rourke have done a remarkable job of showing off the rich interplay between pure mathematics and computing that drives our research community. There really is nothing else like this on the market."--Jeff Erickson, University of Illinois, Urbana-Champaign
