From Proving to Computing
Everywhere on this ladder so far, geometry has been something you reason about: you prove a triangle is congruent, you classify a conic, you compute a curvature by hand. Computational geometry asks a different question. Given thousands or millions of points handed to a computer, what is an actual procedure — a finite recipe of steps a machine can run — that produces a geometric answer, and how slow does that recipe get as the input grows? The shapes are the same shapes you already know; what is new is that we now care about the cost of finding them.
The second guide of this rung built up the language of convexity and polytopes — sets where the segment between any two members stays inside, and the higher-dimensional cousins of polygons. We lean directly on that here. The first object we will compute lives entirely in that world: given a finite cloud of points, its convex hull is the smallest convex set that contains them all. Picture the points as nails hammered into a board and snap a rubber band around the outside; when it relaxes, the taut polygon it traces is the convex hull. Some nails end up on the boundary (the corners), the rest sit harmlessly inside.
Computing the Convex Hull
How do you actually find the hull in the plane? The most intuitive method is the gift-wrapping idea. Start at the point you are certain is a corner — say the lowest one. From there, sweep a ray around and find the next point such that every other point lies on one side of the line through the two; that line is a supporting line, touching the cloud without cutting into it. Pivot to that new point and repeat, wrapping a string tight around the outside until you return to where you began. It is exactly how you would tie a parcel by hand.
Gift-wrapping is honest but can be slow: if the hull has h corners it costs about O(n h), and when almost every point is a corner that degrades toward O(n^2). A cleverer recipe, the Graham scan, does better. Sort the points by the angle they make from a fixed bottom point, then walk through them once, and at each step ask a single question about the last three points: do they turn left or right? A left turn keeps the new point; a right turn means the middle point was a false corner, so pop it off and re-check. Each point is pushed and popped at most once, so after the initial sort the walk is linear — the sort dominates, giving the celebrated O(n log n).
The single test at the heart of Graham scan.
For three points A, B, C taken in order, look at
the cross product of AB and BC:
cross = (B - A) x (C - B)
= (Bx-Ax)(Cy-By) - (By-Ay)(Cx-Bx)
cross > 0 : left turn (keep B, it is a real corner so far)
cross < 0 : right turn (B was a false corner; pop it)
cross = 0 : the three points are collinear (a tie to handle carefully)
No angles, no square roots -- just one signed area.Carving Up the Plane: The Voronoi Diagram
Now a second, very different-feeling question. Scatter a handful of points across the plane — call them sites, perhaps post offices in a city. For every location in the city, which post office is nearest? Colour each location by the answer, and the colours fill the plane in connected blocks: one territory per site, the set of all places for which that site is the closest. This partition is the Voronoi diagram, and it is one of the most quietly ubiquitous structures in all of geometry, turning up in everything from cell-phone coverage to the packing of biological cells.
The boundaries are not mysterious — you can read them straight off something you learned early on this ladder. Consider just two sites, P and Q. A point is equidistant from both exactly when it lies on the perpendicular bisector of segment PQ. On one side of that line P is closer, on the other Q is closer. So with only two sites the plane splits cleanly into two half-planes along their perpendicular bisector. Every wall in a full Voronoi diagram is a piece of a perpendicular bisector between two neighbouring sites; every corner where three walls meet is a point equidistant from three sites at once.
Each territory is itself a convex region — an intersection of half-planes, exactly the kind of object the convexity guide prepared you for. The diagram can be computed remarkably fast: an elegant sweeping technique known as Fortune's algorithm builds the whole thing in O(n log n), the same cost as sorting. A small honesty: that diagram lives in ordinary flat, Euclidean distance. Change the notion of 'nearest' — to driving time along streets, or to distance on a curved surface — and the walls bend into curves and the clean perpendicular-bisector picture is only the starting point, not the final word.
Two Sides of One Coin: Delaunay
Here is where the chapter turns beautiful. Take your Voronoi diagram and do one thing: whenever two sites share a wall — that is, their territories are neighbours — draw a segment connecting those two sites. The web of segments you get is the Delaunay triangulation. It carves the convex hull of the sites into triangles, and it is the exact geometric dual of the Voronoi diagram: Voronoi corners become Delaunay triangles, Voronoi walls become Delaunay edges. The two diagrams carry identical information, dressed in opposite clothes — one a partition into regions, the other a network of triangles.
Why prize this particular triangulation out of the many ways to cut a point set into triangles? Because it is the 'fairest' one. The Delaunay triangulation has the empty-circle property: for every triangle in it, the circle drawn through that triangle's three vertices contains no other site inside it. An equivalent way to say it is that, among all possible triangulations, Delaunay makes the smallest angles as large as possible — it shuns thin, sliver triangles in favour of fat, well-shaped ones. That is precisely what you want when you mesh a shape for engineering simulation or drape a smooth surface over scattered terrain data.
The dual dictionary (sites in the plane, no four on a common circle): VORONOI <--> DELAUNAY --------------------- --------------------- one site <--> one vertex wall between two sites <--> edge joining the two sites corner of three walls <--> triangle on three sites region around a site <--> the triangles touching that vertex Empty-circle test for a candidate triangle: its circumscribed circle must contain no other site inside.
Lifting, Limits, and Where It Goes
These ideas do not stay trapped in the plane, and the way they climb upward is genuinely surprising. Take your points in the plane and lift each one straight up onto a paraboloid — send the point (x, y) to the height x^2 + y^2 in three dimensions. Then compute the convex hull of those lifted points in space and look only at its underside. Project that lower hull back down to the plane, and you get exactly the Delaunay triangulation. The empty-circle property in the plane becomes the plain statement 'this face is on the bottom of the hull' one dimension up. Two problems that looked unrelated are revealed to be the same problem in disguise.
Be honest about the limits, though. In the plane and in three dimensions these structures are cheap and friendly. But the convex hull of n points in d dimensions can have a number of faces that grows like n raised to a power of d — it can explode combinatorially as dimension rises. So 'just run the algorithm' stops being good advice in high dimensions, which is one face of the famous curse of dimensionality. Nearest-neighbour and hull questions that are trivial on a map become genuinely hard in the hundred-dimensional spaces where modern data lives, and much current research is about clever approximations rather than exact answers.
Step back and notice what has happened across this guide. The convex hull is a polytope from the previous guide, now something a machine can build; the Voronoi diagram is woven from perpendicular bisectors you met near the start of the ladder; the bridge between them is the cross product from the vectors rung. Computational geometry did not invent new shapes — it took the shapes you already understand and asked, with engineering seriousness, how to find them fast and correctly. That blend of old geometry and honest cost accounting is exactly the modern frontier this rung is here to show you, and the next guide carries the story into the strange world of fractals.