info prev up next book cdrom email home

Steiner's Segment Problem

Given $n$ points, find the line segments with the shortest possible total length which connect the points. The segments need not necessarily be straight from one point to another.

For three points, if all Angles are less than 120°, then the line segments are those connecting the three points to a central point $P$ which makes the Angles $\left\langle{A}\right\rangle{}PB$, $\left\langle{B}\right\rangle{}PC$, and $\left\langle{C}\right\rangle{}PA$ all 120°. If one Angle is greater that 120°, then $P$ coincides with the offending Angle.

For four points, $P$ is the intersection of the two diagonals, but the required minimum segments are not necessarily these diagonals.

A modified version of the problem is, given two points, to find the segments with the shortest total length connecting the points such that each branch point may be connected to only three segments. There is no general solution to this version of the problem.

© 1996-9 Eric W. Weisstein