Discrete geometry is a relatively new development in pure mathematics, while computational geometry is an emerging area in 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.

* 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). To obtain access, please e-mail: [email protected]

page intentionally left blank POLYGONS Polygons are to planar geometry as integers are to numerical mathematics: a discrete subset of the full universe of possibilities that lends itself to efficient computations. And triangulations are the prime factorizations of polygons, alas without the benefit of the “Fundamental Theorem of Arithmetic” guaranteeing unique factorization. This chapter introduces triangulations (Section 1.1) and their combinatorics (Section 1.2), and then applies these

are collinear, then any triangulation of S has exactly 2k + h − 2 triangles and 3k + 2h − 3 edges. Proof. Let T be a triangulation of the point set S, and let t be the number of triangles of T. We know T subdivides the plane into t + 1 faces, t triangles inside the hull and the face outside the hull. Each triangle has three edges, and the outside face has h edges. Since each edge touches exactly two faces, (3t + h) double counts edges; so there are exactly E = (3t + h)/2 edges. Applying Euler’s

Figure 3.13. (a) The flip graph of a convex pentagon and (b) the 3D associahedron. 75 76 CHAPTER 3. TRIANGULATIONS Theorem 3.39. There exists a convex n-dimensional polytope1 called the associahedron whose vertices and edges form the flip graph of a convex (n + 3)-sided polygon. The k-dimensional faces of this polytope are in one-to-one correspondence with the diagonalizations of the polygon using exactly n − k diagonals. Notice that the vertices of this polytope (the “faces” of dimension

− p ≤ x − q }. If S has numerous sites, then we need to compare the distances of points between p and all other sites of S. This yields the following result: Theorem 4.1. The Voronoi region Vor( p) is the intersection of all halfplanes H( p, q), where q is any other site in S. One of the fundamental results of discrete geometry is as follows: 99 100 CHAPTER 4. VORONOI DIAGRAMS Theorem 4.2. The intersection of any (not necessarily finite) set of convex objects is convex. Proof. Let {Xi | i ∈

0}. Compare the Minkowski sum of the two polygons P1 ⊕ (−R) in Figure 5.12(b), the convolution curve ∂ P1 ∗ ∂(−R) in Figure 5.14(b), and the winding number partition of this curve in Figure 5.15(b). The 5.4 CONVOLUTION OF CURVES (a) (b) +2 +1 +1 +1 +2 0 +2 0 0 Figure 5.15. Winding numbers in regions determined by self-intersecting counterclockwise curves. positive winding number values of the convolution curve precisely mark the Minkowski sum. Exercise 5.22. What is the minimum