↩ back to Minimum Spanning Trees
Euclidean MST already handles the case where a
graph's vertices are points in the plane and edge weight is straight-line distance, by restricting
Kruskal to the point set's Delaunay
triangulation instead of every n(n-1)/2 pair. A common variant swaps in a
different distance instead: L1, or Manhattan distance —
|x₁-x₂| + |y₁-y₂|, the cost of moving along a grid of streets
rather than through open space, the same metric this site's own
A* and ALT
Algorithm pages already use as a grid heuristic. The obvious move is to reuse Euclidean MST's
own shortcut wholesale — build the same Delaunay triangulation, just re-weight its edges by L1
distance instead of straight-line distance — but that doesn't actually work: Delaunay triangulation
is built entirely from circumcircles, a Euclidean notion with no reference to which metric
finally prices an edge, and a small stress check confirms the mismatch is real, not theoretical —
across 5,000 random small point sets, restricting to the Euclidean Delaunay triangulation before
running Kruskal with Manhattan weights landed on the wrong total in about 1% of them. A different
metric needs its own geometric shortcut, built around what actually makes an edge safe to discard
under L1 distance specifically: splitting each point's neighborhood into 8 octants
and keeping only the nearest point in each one.
Seven 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 and
Euclidean MST demos, just fed Manhattan-distance edge
weights instead of Euclidean ones. Octant nearest-neighbor is the point of this
page: 15 candidate edges instead of all 21 possible pairs, same resulting tree, total weight
1144. Complete graph is the naive baseline: all 21 pairs, same
resulting tree, more sorting for no better an answer. 4-quadrant shortcut looks
like a reasonable simplification of the same idea — split the neighborhood into 4 quadrants instead
of 8 octants, one nearest neighbor each — but it isn't guaranteed to contain the true tree, and on
these exact 7 points it doesn't: watch the final total weight land at 1160, heavier
than the other two, with no error or warning anywhere in the run.
Define a point q's octant relative to p by three
independent bits: the sign of dx = qx - px, the sign of dy = qy - py, and
whether |dx| ≥ |dy| — 2 × 2 × 2 = 8 regions, splitting each of the four
quadrants in half along its diagonal. For every point p and every one of its 8
octants, find the point q in that octant minimizing |dx| + |dy| (ordinary
Manhattan distance, not a different measure) and keep (p, q) as a candidate edge. The
claim: the true Manhattan minimum spanning tree only ever uses edges from this candidate set, at
most 8 per point.
The reason an octant (not a full quadrant) is the right unit is a domination argument specific to
L1 distance. Take any point p and any octant where, say, dx ≥ dy ≥ 0
(the "east" octant — dx dominates, both non-negative; the other 7 are the same argument reflected).
Suppose r is the octant's nearest point to p, and q is any
other point in that same octant. Because both r and q sit in the region
where the x-offset dominates the y-offset, walking from p through r to
q never backtracks in either coordinate direction relative to going straight from
p to q — the detour through r costs exactly
dist(p, r) + dist(r, q), and octant membership guarantees this equals
dist(p, q) exactly, not merely bounds it (the staircase from p to
q can always be routed through r for free). So for any spanning tree
that connects p directly to some farther point q in the same octant while
leaving the closer r to be reached some other way, rerouting that edge through
r — replacing p–q with p–r and connecting
q in via r instead — never increases total weight. Only the single
nearest point per octant can ever be the direct target of an edge from p in a minimum
tree; every farther point in the same octant is always reachable at least as cheaply by relaying
through it.
Verified across 20,000 random point sets (3 to 60 points each, both small hand-sized instances and larger ones): a Kruskal run restricted to the octant candidate set matched a brute-force Manhattan MST computed over the full complete graph in all 20,000, 0 mismatches. The candidate count also stays linear in practice, not just in the worst-case bound: at 1,000 random points, the deduplicated octant edge set has about 5.3 candidate edges per point, not the theoretical worst case of 8, since many of a point's 8 octant winners are shared with a neighbor's own proposal for the reverse edge.
octantEdges builds the candidate set described above; kruskalOn is
Kruskal's own reference implementation, unmodified, fed
Manhattan-distance weights on a shorter edge list:
function manhattan(a, b) { return Math.abs(a.x - b.x) + Math.abs(a.y - b.y); }
function octant(p, q) {
const dx = q.x - p.x, dy = q.y - p.y;
const sx = dx >= 0 ? 1 : 0;
const sy = dy >= 0 ? 1 : 0;
const dom = Math.abs(dx) >= Math.abs(dy) ? 1 : 0;
return sx + ',' + sy + ',' + dom; // 8 possible keys
}
function octantEdges(points) {
const n = points.length;
const edgeSet = new Map();
for (let i = 0; i < n; i++) {
const best = new Map(); // octant key -> { dist, j }
for (let j = 0; j < n; j++) {
if (i === j) continue;
const key = octant(points[i], points[j]);
const d = manhattan(points[i], points[j]);
if (!best.has(key) || d < best.get(key).dist) best.set(key, { dist: d, j });
}
for (const { j } of best.values()) {
const a = Math.min(i, j), b = Math.max(i, j);
edgeSet.set(a + '-' + b, [a, b]);
}
}
return [...edgeSet.values()]; // O(n) edges in practice, at most 8n before dedup
}
function manhattanMST(points) {
const edges = octantEdges(points).map(([a, b]) => ({ a, b, w: manhattan(points[a], points[b]) }));
return kruskalOn(points, edges); // ordinary Kruskal, unmodified — see the Kruskal's Algorithm page
}This is the straightforward O(n²) version — for every point, scan every other
point to find each octant's winner. A real implementation gets the same candidate set in
O(n log n) instead, by rotating the plane 45° and running one coordinate-sorted
sweep per octant direction with a balanced search structure standing in for "nearest not-yet-beaten
point so far" — the same practical-vs-optimal trade
Euclidean MST's own Complexity section
makes for Delaunay triangulation, kept simple here for the same reason: this page's demo only ever
runs on 7 points, where the asymptotic difference is invisible either way.
Merging two octants into one quadrant silently drops a required edge, even though the
naive shortcut still finishes and still returns a valid-looking spanning tree. On this
page's own 7 points, the true minimum spanning tree needs both point 2's closest neighbor in its
"east" octant (point 0, distance 112) and a separate edge connecting points 1 and 2
(distance 176) — but 1 and 2 sit in the same quadrant as points 0 and 2 from point 2's
perspective, just different octants (0 has dx ≥ dy, 1 has dy > dx).
A 4-quadrant shortcut keeps only the single nearest point per quadrant, so from point 2's
perspective it keeps the edge to 0 (dist 112, cheaper) and silently discards the candidate edge to
1 entirely. Point 1 doesn't rescue it either — from 1's own perspective, point 3 is quadrant-nearest
(dist 144), so 1 never proposes the 1–2 edge back. The result: Kruskal is fed a graph that's
still fully connected, so it finds some spanning tree without complaint — total weight
1160, using edge 0–1 (dist 192) to link the two halves instead of the true
tree's 1–2 (dist 176), 16 units heavier than the true optimum of 1144. Checked
beyond this one example: across 20,000 random point sets, the 4-quadrant shortcut lands on the
wrong total weight in about 0.5% of them on average — a real but comparatively rare failure rate
for random inputs, which is exactly why this page builds a specific, hand-verified 7-point example
that fails every time rather than leaning on the average alone; a shortcut that's wrong 1 time in
200 is still not a safe default.
The nearest-neighbor measure inside each octant has to be Manhattan distance itself, not
a different-looking stand-in. Selecting each octant's winner by max(|dx|, |dy|)
(Chebyshev/L∞ distance, the natural-looking "how far in the more-extreme coordinate" measure)
instead of |dx| + |dy| looks like it should agree with Manhattan distance's own
ranking inside an octant, since one of the two terms already dominates there — but it doesn't
always: across a separate 20,000-trial sweep, ranking octant candidates by L∞ distance instead
of L1 produced the wrong total weight in about 1.2% of trials, more than double the quadrant
shortcut's own roughly 0.5%, because the two measures can disagree on which of two points in the
same octant is actually closer once the non-dominant coordinate is large enough to matter.
Time: O(n log n) with the rotated-sweep construction described
above (this page's demo and reference implementation use the simpler O(n²)
brute-force octant scan instead, the same trade Euclidean MST makes for its own Delaunay step), plus
O(n log n) to sort the resulting O(n) candidate edges for Kruskal — 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 needing a slot in the sort. Space: O(n) for the candidate edge
set and the resulting tree, against O(n²) to hold every pairwise edge explicitly.
For a decision guide across all eleven 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, and which metric those points use — see Choosing a Minimum Spanning Tree Algorithm.