Rating: 7.9/10.
Book about theorems and algorithms in computational and discrete geometry, which deals with many points and polygons in 2D and higher-dimensional spaces. It starts with triangulations and convex hulls and gives a brief tour of many ideas in the field of geometry and their connections to research mathematics.
Overall, it takes a quick look at many areas but does not go deeply into any topic. While it does describe algorithms for common geometry tasks, such as computing a convex hull or a Voronoi diagram, the focus is more on the mathematical proofs rather than on practical implementation. For example, it describes algorithms intuitively, like start from a point and extending a line until it hits the nearest line segment or something similar, without much information on how to determine where a line crosses another line or how to determine which side of a line a point lies on. It assumes that points are in general position, avoiding issues with collinearity or degenerate cases.
The book has a lot of diagrams in color, making the concept intuitive even when they cover deep research mathematics. This gives the reader an intuitive but not very exact understanding of the problem, which can be both a benefit and a drawback of this book – it goes through many ideas quickly but the reader will not likely be able to implement these algorithms correctly just from the description in this book.
Chapter 1. Each polygon has a triangulation – this can be proved by showing that a polygon with more than three sides has an interior diagonal and using induction. However, not every polyhedron can be broken into tetrahedrons, and determining this is NP-complete. The number of triangulations for a convex polygon is the nth Catalan number; for non-convex polygons, it is fewer but at least 1. A triangulation of an n-vertex polygon always has n-2 triangles, but for tetrahedralization, this is not the case, eg a cube can be turned into either 5 or 6 tetrahedrons.
The art gallery problem is to determine how many guards are needed to cover a polygon. For convex and star polygons, 1 guard is sufficient. For comb-shaped polygons, a lower bound of n/3 guards is needed, and n/3 is always sufficient. Through vertex coloring, it is always possible to obtain an optimal bound by placing guards at vertices and not in the interior. In 3D, even placing a guard at every vertex is not enough to guarantee coverage, and the Seidel polyhedron is a counterexample.
Scissors congruent if a polygon can be cut into pieces and reassembled into another. The Bolyai-Gerwien theorem states that any two polygons of equal area are scissors congruent; the proof works by breaking the polygons into triangles and then into rectangles, demonstrating that rectangles of equal area can transform into each other. In 3D, not all polyhedra are scissors congruent; if they have different Dehn invariants, then they are not scissors congruent.
Chapter 2. A convex hull is the minimum convex region that contains a set of points. In many algorithms, we will assume general position, so ignore edge cases like assuming you can sort all points by their x-coordinate, that no three points are collinear or that no four points lie on the same circle (as these conditions can cause issues with algorithms). While such conditions should not occur when points are generated randomly, they often appear in real-world data. General position means that no algebraic dependencies exist between points.
The incremental algorithm begins with the three points sorted by their x-coordinate, and the first 3 points form the initial convex hull. When adding a new point, identify the two edges from the point that are tangent to the existing convex hull, then add the point and remove all existing points between these two points. This algorithm has an O(n^2) running time because, in the worst case, you must check all n edges when adding a new point.
A slightly better algorithm is the gift wrapping algorithm. After adding a hull point, find the point that has the maximum angle to the existing hull. This algorithm has a time complexity of O(nh), where h is the size of the output hull. The Graham scan is an O(n log n) algorithm. First, sort the points in clockwise order, then iterate through the points in that order. If a point results in a left turn, keep the point; if it results in a right turn, delete the last point.
A lower bound for a convex hull is O(n log n), since a faster algorithm would imply a faster-than-analog algorithm for sorting, which is known to be impossible. The divide-and-conquer algorithm provides another O(n log n) convex hull algorithm. First, sort the points, then separate them into two halves, find the convex hull of each half, and merge them. The merge step can be done in linear time by walking successively along the two hulls until a tangent line is found, after which the points between the tangent lines on both hulls are deleted. In three dimensions, both the incremental and divide-and-conquer algorithms can be generalized with the same time complexity but there is no way to extend the Graham scan algorithm, as there is no concept of clockwise order in 3D.
Chapter 3. A triangulation splits a point set into non-crossing edges, i.e., triangles. The “triangle-splitting” algorithm first finds the convex hull, but then for each interior point, it adds three edges to the triangle that contains it. The incremental algorithm first finds the convex hull, then adding points one at a time and connecting two edges to the points that are visible to it (similar to the convex hull incremental algorithm). Every triangulation has the same number of triangles and edges, which is determined by the number of points on the hull and the interior.
The flip graph is where each triangulation is a node, and two triangulations are connected on the graph if they can be transformed by adding one edge and then removing one edge; it is possible to prove that the flip graph is always connected. In 3D, the tetrahedralization always exists for a point set; for a polyhedron, the flip graph can be defined similarly, but it is unknown whether it is always connected. The flip graph of a convex polygon forms a polytope called an associahedron, which has some deep mathematical properties.
The Delaunay triangulation is the one that avoids “skinny” triangles as much as possible; that is, it has the smallest lexicographic order of the edges in sorted order. This can be obtained by starting with any triangulation and then flipping edges that reduce the smallest angles, and it can be proven that this greedy algorithm leads to a unique global optimum. The Delaunay triangulation has the property that no point is on the interior of any circumcircle of the other points.
Some special triangulations include the minimum weight triangulation problem, which aims to find the triangulation that has the least sum of edge lengths. It turns out that this is neither the Delaunay triangulation nor one that uses a greedy algorithm that takes the shortest edge at each step; in fact, finding the minimum weight triangulation is NP-hard. A compatible triangulation is when you have two point sets and are required to find a triangulation of both such that there is a bijection between the points and the edges match in the bijection. For this to be possible, it is necessary for them to have the same number of points on the convex hull, but it is unknown whether or not this is always sufficient.
Chapter 4: A Voronoi region of a site is a set of points that are closest or equidistant to the site. The Voronoi diagram is the boundary of these regions, represented by a collection of vertices and edges. Each Voronoi region is an intersection of half-planes; therefore, each Voronoi region is convex, and Voronoi vertices are circumcenters of sets of three points that do not contain another point in the interior. Assuming that points are in general position, all Voronoi vertices will have degree three. Voronoi edges can be of finite or infinite length, occasionally forming an infinite line that extends infinitely in both directions. Both the number of Voronoi vertices and edges are O(n).
An incremental algorithm for constructing a Voronoi diagram in O(n^2): assume there is a Voronoi diagram for some points, and then add a new site in an existing Voronoi region. Construct the perpendicular bisector to the closest site, extend it to both edges, and proceed until the Voronoi region is constructed around the new site, deleting the old edges.
The dual graph of a Voronoi diagram is formed by connecting sites whose Voronoi regions are adjacent. This triangulation is the Delaunay triangulation of the sites. In fact, there is a remarkable and deep connection between Delaunay triangulations, Voronoi diagrams, and convex hulls. The convex hull of a set of points in 3D projects to a Delaunay triangulation when projected onto the plane, and the outer envelope corresponds to the Voronoi diagram. Therefore, since we have an O(n log n) algorithm for the convex hull in 3D, this leads to an O(n log n) algorithm for both the Voronoi diagram and the Delaunay triangulations, instead of the O(n^2) algorithm that we constructed earlier.
Chapter 5. The medial axis of a convex polygon is a set of points that are equidistant to multiple points on the polygon, forming a set of lines in the interior. The medial axis can be constructed in O(n log n) time by constructing angle bisectors one at a time and removing vertices as they become irrelevant. For non-convex polygons, however, each time there is a reflex vertex, it creates a nonlinear parabolic arc as a medial axis, which complicates things. Therefore, an alternate definition called the straight skeleton, which is similar in idea to the medial axis but consists of all straight lines instead of possibly parabolic arcs, is used. However, this only works in 2D, and the definition cannot easily be generalized; the algorithm for constructing it has a slower time complexity than that for the medial axis.
The Minkowski sum is defined as an expanded version of a point set by another, and this can be applied to two polygons to determine whether a shape like a circle can fit through the gaps between them. For the curve shortening problem, the most obvious method is a midpoint transform applied to a polygon (connecting the midpoints of each line segment), which always makes it shorter but sometimes introduces crossings. A more sophisticated method is a curve-shortening flow, which evolves a curve based on its curvature, which guarantees non-crossing even for highly non-convex shapes. It is possible to define a discrete variant of the curve shortening flow that moves each vertex according to the positions of the locally neighboring vertices, which avoids self intersection in the end but may have intermediate steps with self-intersections. The curve shortening flow is structurally similar to the Ricci flow, which models how loops in 3D manifolds contract to a point. To solve the Poincaré conjecture, Perelman developed techniques to avoid singularities during the construction process, which is similar to the problem of avoiding self-intersections during curve shortening. The curve reconstruction problem is finding a line or a surface that contains a set of points—in other words, connecting the dots. This can be done with the CRUST algorithm, which uses Voronoi diagrams and Delaunay triangulations, and the correctness depends on certain bounds on how many sample points are given.
Chapter 6. A regular polyhedron is defined as a polyhedron where all faces are regular polygons, and each vertex is adjacent to the same number of faces. Euclid proved that there are only five regular polyhedrons, called the Platonic solids. A polyhedron is composed of vertices, edges, and faces, and it must be locally homeomorphic to a disk, meaning that faces cannot meet at a single point, for example. Additionally, they must be globally connected, so while its surface may have holes like a torus, it cannot have an internal cavity. If a polyhedron is homeomorphic to a sphere, then Euler’s formula states that V – E + F = 2; for polyhedrons not homeomorphic to a sphere, the genus is the number of holes in it, and the Euler characteristic is V – E + F, which has a simple relationship to the genus.
The Gauss-Bonnet theorem states that the integral of the curvature of any surface is constant and depends only on its genus. Therefore, any surface homeomorphic to a sphere has the same total curvature. The discrete polyhedral version of the Gauss-Bonnet theorem defines the curvature by planar angles at each vertex, and again, the sum only depends on the genus. Cauchy’s rigidity theorem asserts that if two convex polyhedra have all faces congruent, then the polyhedra themselves are congruent; this theorem does not hold for non-convex polyhedra. Convex polyhedra are rigid, meaning they cannot be deformed into another configuration without bending. However, it has been discovered that non-convex polyhedra can be flexible, although their volume does not change as they flex.
A net is an unfolding of a polyhedron onto the plane without overlap. Some non-convex polyhedra do not have nets, and it is not known whether every convex polyhedron has a net. Finding the shortest path along a polyhedron can be done using Dijkstra’s algorithm, but the details are quite complex: reaching a node is when the frontier hits a side of a new edge, and paths are grouped by sequences of edges that they cross. A geodesic is a curve on a surface that is everywhere locally the shortest path, although it is not always a global shortest path. It has been proven that every surface homeomorphic to a sphere has at least three closed geodesics, but this is not true for polyhedra unless we relax the definition of a geodesic to a quasigeodesic.
Chapter 7: Configuration space (or state space) is a set of different system states, and we would like to know how to move from one state to the next, eg, moving a robot across a room with obstacles. If only translation is allowed, this can be done by finding the Minkowski sums and determining a path through the space not covered by obstacles. When rotation is allowed, it is possible to divide the space into cells within which an object can move freely; when the object rotation passes a critical angle, the combinatorial structure of the cell changes; these can be represented in a graph where you can search for the shortest path between configurations that are combinatorially different.
In the case of chains of robot arms, consider a configuration space as an n-dimensional space with one dimension for each angle of movement. The robot arm needs to find a path through the space to get to the desired configuration without colliding with obstacles. If collisions with itself is also required to avoid, this leads to exponentially many pairs to check, making it practical only for a small number of joints. The reachability region for a chain of straight arms is annulus (region between two concentric circle)s because the space near the middle may not be reachable if one arm is longer than the rest combined.
Another problem is the ruler folding problem, where a polygonal chain is foldable into a length that is an L. This turns out to be NP-complete by reduction from the set partition problem. The problem of whether a chain can lock into a configuration that cannot be straightened without passing through itself: this can never happen in two dimensions, but it is possible in three dimensions. The final sections of this chapter examine the topological structure of configuration spaces, eg, from the possible degrees of freedom of joints, one can form a surface that is homeomorphic to a sphere or a torus. It can be proven that the configuration space of a regular pentagon is a genus-four surface.
