On the Steiner Ratio in 3-space

W.D. Smith, NECI
J.M. Smith, University of Massachusetts;

12/01/92

ABSTRACT:
The ``Steiner minimal tree'' (SMT) of a point set $P$ is the shortest network
of ``wires'' which will suffice to ``electrically'' interconnect $P$. The
``minimum spanning tree'' (MST) is the shortest such network when only
{\it intersite line segments} are permitted. The ``Steiner ratio'' $\rho ( P )$
of a point set $P$ is the length of its SMT divided by the length of its MST.
It is of interest to understand which point set (or point sets) in ${\bf R}^d$
have minimal Steiner ratio. In this paper, we introduce a point set in ${\bf
R}^d$ which we call the ``$d$-dimensional sausage.'' The 1 and
2-dimensional sausages have minimal Steiner ratios $1$ and $\sqrt{3}/2$
respectively. (The 2-sausage is the vertex set of an infinite strip of abutting
equilateral triangles. The 3-sausage is an infinite number of points evenly
spaced along a certain helix.) We present extensive heuristic evidence to
support the conjecture that the 3-sausage also has minimal Steiner ratio
($\approx 0.784190373377122$). Also: We prove that the regular
tetrahedron minimizes $\rho$ among 4-point sets to at least 12 decimal
places of accuracy. We find SMTs and putative SMTs for a lot of interesting
3D point sets, such as various polyhedra and point lattices. We show a 3D
converse to Rubinstein and Thomas's 2D proof of Graham's conjecture on
the SMTs of cocircular points. This is a companion paper to D-Z. Du and
W.D.Smith: Three disproofs of the Gilbert-Pollak Steiner ratio conjecture
in three or more dimensions, submitted {\bf Journal of Combinatorial
Theory}. We have tried to devote this paper more to 3D and the other paper
more to general dimension, but the split is not clean.

  KEYWORDS:
GILBERT-POLLAK CONJECTURE, STEINER TREES, STEINER
RATIO, MINIMUM SPANNING TREES, INEQUALITIES, SAUSAGE