Skip to content
PartialComputer Science·1836

Steiner Tree Problem

Connect given points with the shortest possible network, allowing extra junction points.

Formula

Steiner minimum tree
min⁡T⊇P∑e∈T∣e∣,T tree, P⊂V(T)\min_{T\supseteq P}\sum_{e\in T}|e|,\quad T\text{ tree, }P\subset V(T)

Find the shortest tree interconnecting a given set of terminal points, allowing additional Steiner points.

Steiner ratio
ρ2=32≈0.866⟹SMT≥32 MST\rho_2=\frac{\sqrt{3}}{2}\approx 0.866\quad\Longrightarrow\quad \text{SMT}\ge\frac{\sqrt{3}}{2}\,\text{MST}

In the Euclidean plane, a Steiner tree is at least √3/2 times the minimum spanning tree length (Gilbert–Pollak, proved 1990s).

120° angle property
At every Steiner point, exactly 3 edges meet at 120°\text{At every Steiner point, exactly 3 edges meet at }120°

Optimal Steiner points have degree 3 with equal 120° angles — the same geometry as soap film junctions (Plateau's laws).

Summary

The geometric Steiner tree problem asks for the shortest network connecting prescribed terminals, with optional Steiner points that meet at 120-degree angles. Its computational versions are NP-hard, but the visual principle is crisp.

Sources

The Euclidean Steiner tree problem is NP-hard

1977

Steiner minimal trees

1968

On Steiner's problem with rectilinear distance

1992

Videos

Thumbnail for Episode 7 - Steiner Trees

Episode 7 - Steiner Trees

Reducible
Thumbnail for Analog computing with soap films (Steiner tree problem)

Analog computing with soap films (Steiner tree problem)

Chirag Kalelkar