The tree inside the triangulation

Two constructions on the same scatter of points, arrived at from opposite directions.

The first asks for the cheapest network that connects everything: among all the ways of joining the points into one piece, find the one whose total length is least. That is a question about lengths, answered by a greedy rule that repeatedly takes the shortest edge it is allowed to take.

The second asks nothing about lengths at all. It joins two points when their territories touch, and the resulting triangulation has the property that no triangle’s circumcircle holds another point. Circles decide everything and no edge is ever compared with another for length.

Every edge of the tree is an edge of the triangulation. That is not approximately true, not true for most configurations, and not a consequence of the two constructions being related — it is exact, and the proof is three sentences long.

The three sentences #

Suppose $uv$ is an edge of the minimum spanning tree, and consider the circle having $uv$ as a diameter. Claim: it contains no other site.

For suppose some site $w$ were inside it. A point inside the circle on $uv$ as diameter sees $uv$ at an angle greater than a right angle — that is the inscribed-angle theorem, whose whole content is that the angle is exactly a right angle on the circle and larger inside it. In a triangle, the longest side is opposite the largest angle, so $uv$ is strictly longer than both $uw$ and $wv$.

Now delete $uv$ from the tree. The tree falls into two components, one containing $u$ and one containing $v$, and $w$ is in one of them — say the one with $u$. Then $wv$ crosses between the components, so adding it reconnects the tree, and it is shorter than $uv$. The result is a spanning tree of smaller total length, which contradicts the assumption that the original was minimal.

So every tree edge has an empty diametral circle. And an edge with an empty diametral circle is a Delaunay edge, because the diametral circle is one circle through both endpoints containing nothing else, and the Delaunay condition on an edge is exactly that some circle through its endpoints is empty. The containment follows.

The exchange step deserves one more look, because it is where the minimality is actually used and it is easy to read past. Deleting an edge from a tree always leaves exactly two components — that is what a tree is — and any edge joining the two components restores a tree. So the argument does not need to know anything about the rest of the network: it needs one edge crossing one cut, and it has one, because $w$ is on one side and $v$ on the other. The whole of the contradiction lives in that single swap.

That is the cut property, which is the engine of every algorithm for this problem. Prim’s method grows a component and repeatedly takes the shortest edge leaving it; Kruskal’s sorts every edge and takes each one that joins two components. Both are the same statement — the shortest edge across any cut is in some minimum spanning tree — used in two orders, and the proof of that statement is the exchange above with the circle removed.

Notice what the argument never does. It does not construct the triangulation, does not consider any triangle, and does not use any property of the Delaunay condition beyond its definition. The whole of it is the inscribed-angle theorem and the exchange step that every greedy argument about spanning trees uses.

Five graphs, each inside the next #

The tree and the triangulation are not two isolated points; they are two links of a chain, and each link is defined by an emptiness condition on a differently shaped region.

The chain runs:

Nearest-neighbour graph. Join each site to whichever site is closest to it. At most $n$ edges, usually fewer, since a mutual pair contributes one edge rather than two, and it need not be connected — two sites that are each other’s nearest form an island however far the rest of the scatter is.

Minimum spanning tree. Exactly $n - 1$ edges, connected by construction. It contains every nearest-neighbour edge, because if $v$ is nearest to $u$ then no site lies inside the circle centred at $u$ through $v$, and a variant of the exchange argument applies.

Relative neighbourhood graph. Join $u$ and $v$ when no third site is closer to both of them than they are to each other. The forbidden region is the lune — the intersection of the two circles of radius $|uv|$ centred at the endpoints.

Gabriel graph. Join $u$ and $v$ when the circle on $uv$ as diameter is empty. The forbidden region is that circle, which sits inside the lune, so the condition is weaker and there are more edges.

Delaunay triangulation. Join $u$ and $v$ when some circle through both is empty. The weakest condition of all, and the most edges.

It is worth being explicit that the first two links are of a different character from the last three. The nearest-neighbour graph and the spanning tree are defined by comparisons between edges — which is shorter than which — while the last three are defined by a region being empty, with no edge ever compared to another. The chain therefore has a seam in it, and the argument of the previous section is precisely the work of crossing that seam: it converts a statement about lengths into a statement about an empty circle, after which everything is regions and the ordering is free.

Read downwards the regions shrink and the conditions weaken, so the edge sets grow. That is the whole reason the chain nests, and it is a nicer explanation than four separate proofs: each graph is “join two sites when this region is empty”, and the graphs are ordered because the regions are.

The middle link is where the argument above actually lives. The tree sits inside the Gabriel graph because a tree edge has an empty diametral circle, which is the Gabriel condition verbatim; and the Gabriel graph sits inside the triangulation because an empty circle through both endpoints is what a Delaunay edge needs. The three sentences of the last section prove the first of those, and the second is a definition chase.

The same fact read on the diagram rather than the dual #

Everything above is stated about the triangulation. Translating it back to the diagram it is dual to gives a statement that is less useful and more surprising.

Two sites are joined in the triangulation exactly when their cells share an edge, so the containment says: the shortest network never joins two sites whose territories do not touch. Put that way it sounds like something that ought to be obvious, and it is not — the tree is chosen by length, and there is no reason in advance why a long connection across the top of somebody else’s cell should be forbidden.

The reason it is forbidden is the argument above, and the diagram gives it a second reading. If the cells of $u$ and $v$ do not touch, then the segment between them passes through some third site’s cell, and a point in that cell is nearer to the third site than to either end. That is not quite the proof — nearness to the midpoint is not the same as the diametral circle being empty — but it is the right intuition, and it explains why the two conditions turn out to be about the same thing.

What the containment buys #

The gain is a change of size class, and it is worth putting numbers on.

Building the tree by the obvious method means examining every pair, of which there are $n(n-1)/2$ — a quadratic amount of work before any algorithm starts. Building it from the triangulation means examining at most $3n - 6$ edges, because the triangulation is a planar graph and Euler’s relation bounds a planar graph’s edges at three times its vertices. So the recipe is: construct the triangulation in $O(n \log n)$, then run any standard spanning-tree algorithm on a graph with linearly many edges, which costs $O(n \log n)$ again.

That takes a quadratic problem to a near-linear one, and the only ingredient is knowing which edges cannot possibly be in the answer. The triangulation is a certificate of irrelevance: it does not say which edges are in the tree, it says which edges are not worth looking at, and there are only a linear number left.

There is a fourth use, and it is the one that reaches furthest. Walking round a minimum spanning tree — down every branch and back — traverses each edge twice, so it gives a closed tour of all the sites of length at most twice the tree’s. And the shortest tour is at least as long as the tree, because deleting any edge of a tour leaves a spanning path, which is a spanning tree. So the tree’s length brackets the shortest tour between one and two times itself, which is the classical two-approximation for the Euclidean travelling-salesman problem — obtained, by way of the containment above, in near-linear time from a structure built for another purpose entirely.

The same trick applies twice more from the same containment. The nearest-neighbour graph is inside the triangulation too, so all nearest neighbours can be found in $O(n \log n)$ rather than by comparing every pair. And the shortest edge in the whole set — the closest pair of points — is a nearest-neighbour edge, hence a triangulation edge, so the classical closest-pair problem falls out of the same construction.

Who noticed, and why it mattered so much #

The containment is due to Michael Shamos and Dan Hoey, in a 1975 paper that is usually cited as the moment computational geometry became a subject rather than a collection of tricks.

The setting is worth reconstructing. At that date the standard treatment of geometric problems on $n$ points was to enumerate pairs or triples, which put almost everything at $n^2$ or $n^3$, and the standard opinion was that this was intrinsic — a problem about pairs surely requires looking at pairs. Shamos and Hoey’s contribution was a single structure with three uses: build the diagram once in $O(n \log n)$, and closest pair, all nearest neighbours and the minimum spanning tree all come out of it.

The intellectual move is the one worth taking away, and it is not geometric. They did not find a faster way to compare pairs. They found an object of linear size which provably contains every pair that could matter, and then did the obvious slow thing to the small object. That pattern — build a compact certificate, then be as naive as the problem allows inside it — is now everywhere in algorithms, and this is close to its first clean instance.

It also fixed the subject’s habits. Almost every result in planar computational geometry since has the shape reduce to a linear-size structure, and the structures are variations on this one: the diagram, its dual, the hull, and the lifting map that ties them together. The reason the ladder’s earlier rungs are worth climbing is largely that they are the tools this rung spends.

Where it fails, and where it does not #

It fails in three dimensions, and not in the way one would guess. The containment itself survives — the same argument works with spheres in place of circles, so the tree of points in space is a subgraph of the three-dimensional Delaunay triangulation. What fails is the payoff: a Delaunay triangulation of $n$ points in space can have $\Theta(n^2)$ tetrahedra, and points on a moment curve achieve it. So the certificate of irrelevance certifies nothing, and the quadratic problem stays quadratic.

That is an unusually clean example of a proof surviving a generalisation while the reason for caring about it does not. The theorem is a theorem in every dimension; the algorithm is an algorithm in two.

The dimension-two case is not a lucky accident either, and the reason is planarity. A triangulation of points in the plane is a planar graph, and a planar graph has linearly many edges because of Euler’s relation rather than because of any property of the Delaunay condition. Take away planarity — which is exactly what the third dimension does — and the bound goes with it. Every step of the algorithmic argument is therefore leaning on a topological fact about the plane rather than on a metric one, which is not visible from inside the two-dimensional case.

It does not fail on ties, though it becomes fussier. If several edges have the same length the minimum spanning tree is not unique, and the correct statement is that some minimum spanning tree is a subgraph of some Delaunay triangulation. Four concyclic points make both objects ambiguous at once, which is the degeneracy the lifting map relocates rather than removes.

And it says nothing about the shortest network. The minimum spanning tree is the shortest network joining the sites using only the sites as junctions. Allowing extra junction points gives the Steiner tree, which can be shorter — by up to about thirteen per cent — and whose extra points are not sites, so no statement about the triangulation’s edges constrains it. The Steiner problem is NP-hard, the spanning-tree problem is nearly linear, and the whole distance between them is whether new points may be invented.

What the pictures cannot show #

Every picture here is one scatter, and the theorem is about all of them. A containment that holds in two drawings is two instances. What makes it a theorem is the three sentences, and those are prose; the figures check the containment edge by edge on what they draw and can do no more than that.

The greedy choice is invisible. The tree is drawn as a finished object, and the argument that produced it is a sequence of decisions — take the shortest edge that does not close a cycle, repeat. A picture of the finished tree gives no hint that a rule of that shape produced it, and the exchange argument in the proof is about a tree that is not drawn, namely the shorter one that would exist if a tree edge had a site in its circle.

Nothing shows why the two constructions agree. The proof is an exchange argument about a tree that does not exist — the shorter one that would be available if a tree edge had a site inside its circle — and a picture can only ever draw the arrangement that is not refuted. The figure above comes closest by drawing an edge that is refuted, together with the two shorter edges that refute it, and even there the tree the swap would produce is left to the reader.

And the empty circles are drawn for four edges of nineteen. Drawing all nineteen produces a page of overlapping discs in which nothing can be read. The assertion covers every edge; the drawing covers the ones that fit.

Where the ladder goes next #

This rung closes the loop the anchor’s first essay opened: the diagram was introduced as a way of dividing a plane, and it turns out to be a way of finding a graph. Every construction on the ladder has now been used for something outside itself — the hull for the theory, the centroid for the iteration, the weights for the model, and the triangulation for the tree.

What is left unwritten and named here as a debt is the medial axis: the Voronoi diagram of a shape’s boundary rather than of a finite set of points, which is what a skeleton of a shape is and what makes the construction reach continuous objects. Nothing above touches it.

Sideways, the counting of spanning trees rather than their construction is a determinant, and the labelled trees on a small point set are counted exactly by a formula with no geometry in it at all.

What is worth carrying away #

The most useful thing one object can say about another is which possibilities are not worth considering.

The triangulation does not compute the tree, does not agree with it, and does not resemble it — it has more than twice as many edges. What it does is rule out every edge that could not be in the tree, and there turn out to be quadratically many of those and only linearly many left. A structure that answers no about most candidates is more valuable here than one that answers yes about a few.

The habit worth taking is to look for the containment before looking for the algorithm. The nesting chain above was assembled by asking, of five different graphs, what region must be empty for this edge to exist — and once that is the question, the ordering is immediate and five separate proofs collapse into one observation about which regions sit inside which.