↩ back to Minimum Spanning Trees
Kruskal's, Prim's, and
Borůvka's algorithms all treat their input as an arbitrary
weighted graph — nothing about the cut property they lean on cares where the weights came from, so
none of them can do better than looking at every edge at least once. But a common special case hands
over far more structure than "an edge list": the graph's n vertices are literal points in
the plane, and the weight of every possible edge is just the straight-line distance between two points.
Feed that into Kruskal directly and the "obvious" edge list has n(n-1)/2 entries — every
pair of points, since any two points are technically connectable — which for a few thousand points is
already tens of millions of edges to sort before Kruskal even starts choosing. The Euclidean minimum
spanning tree is the same problem, with a much smaller honest edge list: it turns out that the true
minimum spanning tree of a planar point set is always a subgraph of that point set's
Delaunay triangulation, which has at most
3n - 6 edges — linear in n, not quadratic. Build the triangulation once,
run ordinary Kruskal on only those edges, and the result is provably identical to running Kruskal on
the full n(n-1)/2-edge complete graph. This isn't a fifth way to compute a different
tree — it's the same tree Kruskal, Prim, and Borůvka already build, reached by first throwing away
every candidate edge that geometry guarantees can't be in it.
Eight fixed points. Pick a candidate edge set below, press Load, then Step or Run to watch ordinary cheapest-first Kruskal walk it — identical accept/reject logic to the Kruskal's Algorithm demo, just fed a different edge list each time. Delaunay triangulation is the point of this page: 16 candidate edges instead of all 28 possible pairs, same resulting tree. Complete graph is the naive baseline: all 28 pairs, same resulting tree, more sorting for no better an answer. 3-nearest-neighbor shortcut looks like a reasonable geometric shortcut too — only 13 edges, each point connected to its 3 closest neighbors — but it isn't guaranteed to contain the true minimum spanning tree, and on these exact 8 points it doesn't: watch the final total weight come in heavier than the other two, with no error or warning anywhere in the run.
The proof goes through an intermediate structure, the Gabriel graph: an edge
(u, v) belongs to it exactly when the circle with segment uv as its
diameter — the smallest circle passing through both points — contains no third point of the
set. Claim 1: every edge of the true minimum spanning tree is a Gabriel edge. Suppose
MST edge (u, v) isn't — some point w sits strictly inside uv's
diametral circle. Any point strictly inside a circle sees that circle's diameter at an angle greater
than 90°, so triangle uwv has an obtuse angle at w. A triangle can have at
most one angle that large, and the side opposite the largest angle is always the longest side of the
triangle — so uv, the side opposite the obtuse angle, is strictly longer than both
uw and wv. Now remove (u, v) from the MST: it splits into two
components, one holding u, one holding v. If w is in
u's component, edge (w, v) crosses the identical split at a strictly lower
weight — swapping it in for (u, v) gives a cheaper spanning tree, contradicting that the
original was minimum. w in v's component is the same argument with
(u, w). Either way (u, v) couldn't have been an MST edge after all, so no
real MST edge can have a point inside its diametral circle. Claim 2: every Gabriel edge is a
Delaunay edge. An edge is Delaunay-legal exactly when some empty circle passes
through both its endpoints — the usual definition, via a triangle's circumcircle. A Gabriel edge's own
diametral circle already is one such empty circle (nothing else needs to be checked: it's empty of
other points by definition), so satisfying the stricter Gabriel condition automatically satisfies the
looser Delaunay one. Chain the two claims — MST edges are Gabriel edges, Gabriel edges are Delaunay
edges — and every MST edge is a Delaunay edge, with no edge left out.
The 3-nearest-neighbor shortcut in the demo above fails at exactly the step Claim 1 relies on:
"closest k neighbors" says nothing about whether a longer edge might still be
the only bridge connecting two otherwise-far-apart clusters. Delaunay's guarantee doesn't come from
picking nearby points — the diametral-circle argument works for MST edges of any length, including
the long ones a fixed-k neighbor list would never consider.
delaunayEdges is the identical Bowyer-Watson construction from the
Delaunay Triangulation page, trimmed to return
edges instead of triangles; kruskalOn is Kruskal's
own reference implementation, unmodified, just handed a shorter edge list:
function delaunayEdges(points) {
let triangles = [superTriangle(points)]; // see the Delaunay Triangulation page for superTriangle/inCircumcircle
for (const p of points) {
const bad = triangles.filter(t => inCircumcircle(t[0], t[1], t[2], p));
const edgeCount = new Map();
for (const t of bad) {
for (const [u, v] of [[t[0], t[1]], [t[1], t[2]], [t[2], t[0]]]) {
const key = edgeKey(u, v);
if (!edgeCount.has(key)) edgeCount.set(key, { count: 0, edge: [u, v] });
edgeCount.get(key).count++;
}
}
const boundary = [...edgeCount.values()].filter(e => e.count === 1).map(e => e.edge);
triangles = triangles.filter(t => !bad.includes(t));
for (const [u, v] of boundary) triangles.push([u, v, p]);
}
const real = triangles.filter(t => !t.some(v => v.super));
const edgeSet = new Map();
for (const t of real) {
for (const [u, v] of [[t[0], t[1]], [t[1], t[2]], [t[2], t[0]]]) edgeSet.set(edgeKey(u, v), [u, v]);
}
return [...edgeSet.values()]; // O(n) edges, at most 3n - 6
}
function euclideanMST(points) {
const edges = delaunayEdges(points).map(([a, b]) => ({ a, b, w: dist(a, b) }));
return kruskalOn(points, edges); // ordinary Kruskal, unmodified — see the Kruskal's Algorithm page
}A geometric-looking shortcut isn't automatically a safe one — it has to actually contain
the MST, and "closest few neighbors" doesn't. The 3-nearest-neighbor option in the demo above
reproduces a real, verified failure on this page's own 8 points: Kruskal restricted to the complete
graph or the Delaunay triangulation both land on total weight 668.74 (an 0-3,
3-6, 4-5, 0-1, 5-7, 2-7,
0-7 tree); restricted to the 13-edge 3-nearest-neighbor graph, Kruskal still finds a valid
spanning tree — nothing crashes, no edge count comes up short — but its total weight is
743.83, about 11% heavier, because the true MST's longest edge (2-7, length
164.3) links two points that are each other's closest, more-local neighbors to everyone
except each other, so neither one's fixed-k neighbor list ever offers that edge
as a candidate. A broader stress check confirms this isn't a one-off: across 3,000 random 6-to-25-point
sets, the same 3-nearest-neighbor construction produced the wrong total weight in 626 of them
(≈21%) — frequent enough that "restrict to nearby points" cannot be trusted as a drop-in replacement
for the Delaunay triangulation, even though both look like the same kind of geometric pruning.
The Delaunay triangulation isn't unique when four or more points sit exactly on a common circle — the same caveat the Delaunay Triangulation page's own Pitfalls section makes about its circumcircle test. The Gabriel-graph proof above doesn't depend on which triangulation gets picked in that tie case, since it goes through diametral circles directly rather than through any one triangulation's specific triangles — but a real implementation still inherits Delaunay's own floating-point circumcircle-test precision concerns, not a new problem this page introduces.
Time: O(n log n) total — the randomized-incremental Delaunay
triangulation described on its own page's Complexity section runs in expected O(n log n)
(this page's demo and reference implementation both use the simpler O(n²)
Bowyer-Watson scan instead, the same trade this page's own dependency makes), and sorting the
resulting O(n) candidate edges for Kruskal costs O(n log n) on top — both
terms the same order, so the total stays O(n log n). Feeding the same points to Kruskal
over the complete graph instead costs O(n² log n): O(n²) edges, each one
needing a slot in the sort. Space: O(n) for the triangulation and the
resulting tree, against O(n²) to hold every pairwise edge explicitly.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — when the input is a plain weighted graph versus when it's specifically points in the plane — see Choosing a Minimum Spanning Tree Algorithm.