Textbook in PDF format

Although geometry is as old as mathematics itself, discrete geometry only fully emerged in the twentieth century, and computational geometry was only christened in the late 1970s. The terms discrete and computational fit well together, as the geometry must be discretized in preparation for computations. Discrete here means concentration on finite sets of points, lines, triangles, and other geometric objects, and is used to contrast with continuous geometry, for example, smooth surfaces. Although the two endeavors were growing naturally on their own, it has been the interaction between discrete and computational geometry that has generated the most excitement, with each advance in one field spurring an advance in the other. The interaction also draws upon two traditions: theoretical pursuits in pure mathematics and applicationsdriven directions often arising in computer science. The confluence has made the topic an ideal bridge between mathematics and computer science. It is precisely to bridge that gap that we have written this book.
In line with this goal, our presentation is sprinkled with both algorithms and theorems, with sometimes the theorem serving as the main thrust (e.g., the Gauss-Bonnet theorem), and sometimes an algorithm the primary goal of a section and theorems playing a supporting role (e.g., the flip graph computation of the Delaunay triangulation). As our emphasis is on the geometry of the subject, the algorithms presented in this book are strongly rooted in geometric intuition and insight. We describe the algorithms independent of any particular programming language, and in fact we do not even employ pseudocode, trusting that our boxed descriptions can be read as code by those steeped in the computer science idiom. Thus, no programming experience is needed to read this book. Algorithm complexities are discussed using the big-Oh notation without an assumption of prior exposure to this style of thinking, which is (lightly) covered in the Appendix.
We include many proofs that we feel would interest a mathematically inclined student, presenting them in what we hope is an accessible style. At many junctures we connect to more advanced concerns, not fearing, for example, to jump to higher dimensions to make a relevant remark. At the same time, we connect each topic to applications that were often the initial motivation for studying the topic. Although we include careful proofs of theorems, we also try to develop intuition through visualization. Geometry demands figures!
Some exposure to proofs is needed to gain that mystical mathematical maturity. We invoke calculus only in a few sections. A course in discrete mathematics is the more relevant prerequisite, but any course that presents formal proofs of theorems would suffice, such as linear algebra or automata theory. The material should be completely accessible to any mathematics or computer science major in the second or third year of college. In order to reach interesting advanced topics without the careful preparation they often demand, we sometimes offer a proof sketch (always marked as such), instead of a long, detailed formal proof of a result. Here we try to convince the reader that a formal proof is likely to be possible by sketching in the outlines without the details. Whether the reader can imagine those details from the outline is a measure of mathematical experience. A parallel skill of computational maturity is needed to imagine how to implement our algorithm descriptions.
The book is studded with Exercises, which we have chosen to place wherever they are relevant, rather than gather them at the end of each chapter. Some merely test a grasp of the foregoing material, most require more substantive thought (suitable for homework assignments), and starred exercises * are difficult, often connecting to a published paper. A solutions manual is available to instructors from the publisher.
Polygons
Convex Hulls
Triangulations
Voronoi Diagrams
Curves
Polyhedra
Configuration Spaces
Computational Complexity