\input{defines.tex} \documentstyle{article} \begin{document} \title{Networks Minimizing Length Plus the Number of Steiner Points} \author{Joel Foisy \and Thomas Colthurst \and Chris Cox \and Hugh Howards \and Kathryn Kollett \and Holly Lowy \and \hspace{1in} \and Stephen Root \and \hspace{1in} \and \\ c/o Prof. Frank Morgan \\ Department of Mathematics \\ Williams College \\ Williamstown, MA 01267 \\ Internet: fmorgan@williams.edu} \maketitle \section{Introduction} The Steiner problem seeks to connect a given set of vertices with the shortest network, generally with added vertices called Steiner points. We add a unit penalty for each Steiner point, modeling, for example, the expense of each intersection in a road network. The existence of networks minimizing length plus the number of Steiner points follows from standard compactness arguments. In this paper we prove that four edges may meet at a Steiner point in a minimizing network in $\Re^2$, while five edges cannot. We further show that $2n$ edges may meet in $\Re^{n}$, and that the maximum number of edges which can meet in $\Re^{n}$ grows exponentially. \section{Singularities in networks minimizing length plus the number of Steiner points in $\Re^2$} \label{sec:fives} As we will see in the next section, three and four edges can meet at a point in networks minimizing length plus the number of Steiner points. This section establishes that five edges cannot meet at a Steiner point. \blm If $AB$ and $AC$ are two edges meeting at a point $A$ in a cost minimizing network, then $\angle BAC \geq 60^{\circ}$. \label{lm:lessthan60} \elm \bpf If $\angle BAC < 60^{\circ}$, then $\angle ABC$ or $\angle BCA > 60^{\circ}$. Without loss of generality, take $\angle ABC > 60^{\circ}$. Then $\| AC \| > \| BC \|$, so $AB + BC$ is a cheaper network than $AB + AC$. \epf \begin{figure} \vspace{1.5 in} \special{psfile=fives1.ps 113.5 0 translate} \caption{In a triangle with largest angle $\gamma$, $\| a \| + \| b \| \geq \| c \|(2\cos \gamma + 1)$.} \label{fig:fives1} \end{figure} \blm In $\triangle abc$, (see Figure~\ref{fig:fives1}) where $90^\circ \geq \gamma > \alpha$ and $\gamma > \beta$, $\| a \| + \| b \| \geq \| c \|(2\cos \gamma + 1)$. \label{lm:2cos..} \elm \bpf Without loss of generality, fix $\gamma$ and take $\beta \geq \alpha$. By the law of sines, $$\frac {\| a \|}{\sin \alpha} = \frac {\| b \|}{\sin \beta} = \frac {\| c \|}{\sin \gamma} = \frac {\| a \|}{\sin (\beta + \gamma)}.$$ Therefore, $$\frac {\| a \| + \| b \|}{\| c \|} = \frac {\sin (\beta + \gamma) + \sin \beta}{\sin \gamma}.$$ The minimum value of this expression of varying $\beta$ occurs when $\beta = \alpha$, so $$ \frac {\| a \| + \| b \|}{\| c \|} = 1 + \frac{\sin (2\gamma)}{\sin \gamma} = 2\cos \gamma + 1. $$ \epf \begin{figure} \begin{center} \setlength{\unitlength}{.03in} \begin{picture}(100,100)(0,10) \put(30,20){\line(1,0){40}} \put(20,60){\line(1,-4){10}} \put(20,60){\line(1,1){30}} \put(50,90){\line(1,-1){30}} \put(70,20){\line(1,4){10}} \put(30,20){\line(2,3){20}} \put(20,60){\line(3,-1){30}} \put(50,50){\line(3,1){30}} \put(50,50){\line(0,1){40}} \put(50,50){\line(2,-3){20}} \put(76,40){\makebox(0,0)[l]{$a_{0}$}} \put(67,75){\makebox(0,0)[l]{$a_{1}$}} \put(33,75){\makebox(0,0)[r]{$a_{2}$}} \put(25,40){\makebox(0,0)[r]{$a_{3}$}} \put(50,15){\makebox(0,0)[t]{$a_{4}$}} \put(68,30){\makebox(0,0)[b]{$\gamma_{0}$}} \put(75,63){\makebox(0,0)[r]{$\gamma_{1}$}} \put(45,82){\makebox(0,0)[t]{$\gamma_{2}$}} \put(25,52){\makebox(0,0)[l]{$\gamma_{3}$}} \put(35,25){\makebox(0,0)[l]{$\gamma_{4}$}} \put(50,50){\line(5,-2){14}} \put(60,50){\makebox(0,0)[l]{$\theta$}} \put(58,41){\makebox(0,0)[l]{$\theta$}} \put(53,55){\makebox(0,0)[l]{$\alpha_{1}$}} \put(47,55){\makebox(0,0)[r]{$\alpha_{2}$}} \put(47,48){\makebox(0,0)[r]{$\alpha_{3}$}} \put(50,42){\makebox(0,0)[t]{$\alpha_{4}$}} \put(75,50){\makebox(0,0)[r]{$\beta_{0}$}} \put(55,82){\makebox(0,0)[t]{$\beta_{1}$}} \put(26,63){\makebox(0,0)[l]{$\beta_{2}$}} \put(32,30){\makebox(0,0)[b]{$\beta_{3}$}} \put(65,25){\makebox(0,0)[r]{$\beta_{4}$}} \put(65,57){\makebox(0,0)[b]{$p_{0}$}} \put(49,70){\makebox(0,0)[r]{$p_{1}$}} \put(35,57){\makebox(0,0)[b]{$p_{2}$}} \put(45,34){\makebox(0,0)[b]{$p_{3}$}} \put(56,34){\makebox(0,0)[b]{$p_{4}$}} \end{picture} \end{center} \caption{Five edges cannot meet at a Steiner point in a cost minimizing network.} \label{fig:fives2} \end{figure} \blm If five edges, $p_0, p_1, \ldots , p_4$, meet at a Steiner point in a cost minimizing network, as in Figure~\ref{fig:fives2}, then $\alpha_{i} < 2\tan^{-1} \frac{5}{3\sqrt{3}},$ for all $i \in \{0, 1, \ldots, 4\}$. \elm \bpf Without loss of generality, let $\angle \alpha_0 = 2\theta$ be the largest angle. By a simple calculus minimization argument, $\sum_{i = 0}^{4}\frac{p_{i}}{\|p_{i}\|} = 0$. Consider the components in the $p_0$ and $p_4$ directions: $2\cos \theta + \cos (\theta + \alpha_1) + \cos (\theta + \alpha_1 + \alpha_2) + \cos (\alpha_4 + \theta) = 0$. $\theta$ is maximized if $\alpha_1 = \alpha_2 = \alpha_4 = 60^{\circ}$ by a convexity argument, so $2\cos \theta + \cos (\theta + 60^{\circ}) + \cos (\theta + 120^{\circ}) = 0$, or $\theta = \tan^{-1} \frac{5}{3\sqrt{3}}$, so $\alpha_0 = 2\theta < 87.795^{\circ}$. \epf \bthm Five edges cannot meet at a Steiner point in a cost minimizing network. \ethm \bpf Consider five edges $p_0, \ldots , p_4$ meeting at a Steiner point in a cost minimizing network. $\alpha_0 \geq \beta_0$ and $\alpha_0 \geq \gamma_0$, since otherwise we could substitute as in Lemma \ref{lm:lessthan60}. Now apply Lemma \ref{lm:2cos..} to obtain $\|p_i\| + \|p_{i + 1}\| \geq \| a_i\|(2\cos \alpha_i + 1)$. Then $2\sum_{i = 0}^4 \|p_ i\| \geq \sum_{i = 0}^{4} \| a_i \|(2\cos \alpha_i + 1)$. Without loss of generality, let $a_0$ be the longest side. The cost of the perimeter is $\sum_{i=1}^{4} \| a_{i} \|$, and the cost of five edges meeting at a Steiner point is $\sum_{i=0}^{4} \| p_{i}\| + 1$. Since $\sum_{i = 0}^{4} \alpha_i = 2\pi$, by a convexity argument, $\sum_{i = 0}^{4} \cos \alpha_i$ is minimized when the angles are at the extremum of the domain ($60^{\circ}, 87.796^{\circ}$) This means that $\alpha_i = {60^{\circ}, 60^{\circ}, 64.41^{\circ}, 87.796^{\circ}, 87.796^{\circ}}$, and $\sum_{i = 0}^{4} \cos \alpha_i > 1.5087 > \frac {3}{2}$. Therefore, $$\| a_0 \|(\cos \alpha_0 + \frac{1}{2}) + \sum_{i = 1}^{4}\| a_i \|(\cos \alpha_i - \frac{1}{2}) > 0,$$ so $$\frac{1}{2}\| a_0 \|(2\cos \alpha_0 + 1) + \frac{1}{2}\sum_{i = 1}^{4}\| a_i \|(2\cos \alpha_i + 1 - 2) > 0,$$ and $$\frac{1}{2}\sum_{i = 0}^{4} \| a_i \|(2\cos \alpha_i + 1) > \sum_{i = 1}^{4}\| a_i \|.$$ Recall that $2\sum_{i = 0}^4 \|p_i\| \geq \sum_{i = 0}^{4} \| a_i \|(2\cos \alpha_i + 1)$, so $$\sum_{i = 0}^4 \|p_i\| > \sum_{i = 1}^{4}\| a_i \|,$$ and $$\sum_{i=0}^{4} \| p_{i}\| + 1 > \sum_{i=1}^{4} \| a_{i} \|.$$ But then the cost of five edges meeting at a Steiner point is greater than the cost of the perimeter. Therefore, five edges cannot meet at a Steiner point in a cost minimizing network. \epf \subsection{The Square} \begin{figure} \vspace{3.0in} \special{psfile=squ1.ps 204 0 translate} \special{psfile=squ2.ps 204 108 translate} \special{psfile=squ3.ps 48 0 translate} \special{psfile=squ4.ps 48 108 translate} \caption{The four possible topological types of networks minimizing length plus number of Steiner points on the square. The network in the upper right is never the minimizer, but the other three are minimizing at some scale.} \label{fig:squ} \end{figure} We list the cost minimizing networks on a square to show that three and four edges can meet at a Steiner point in such a network. On the square, there are four topological types which do not have non-adjacent vertices connected by an edge (this is obviously not cost minimizing). These are shown in Figure~\ref{fig:squ}: \begin{enumerate} \item Two Steiner points connected to each other and each connecting adjacent vertices. This is the length minimizing tree, and has cost $C(L) = 2 + (1 + \sqrt{3})L \approx 2 + 2.732L$. \item One Steiner point connecting three of the vertices and a side of the square connecting the fourth. This has cost $C(L) = 1 + (1 + \frac{\sqrt{2}}{2} + \frac{\sqrt{6}}{2}) L \approx 1 + 2.932L$. \item One Steiner point at the center of the square connecting all four vertices. This has cost $C(L) = 1 + 2 \sqrt{2} L \approx 1 + 2.828L$. \item The perimeter method, with no Steiner points and three sides of the square. Here the cost $C(L) = 3L$. \end{enumerate} The network with two Steiner points is the unique network with two Steiner points and four vertices \cite{co:thesis}, and all degenerate cases of it are discussed except for the one which has one vertex of the square connected to each of the other three, which is obviously not cost minimizing. When $L \geq \frac{1}{2 \sqrt{2} - \sqrt{3} -1}$, the length minimizing network is cost minimizing. For $\frac{1}{3 - 2 \sqrt{2}} \leq L \leq \frac{1}{2 \sqrt{2} - \sqrt{3} -1}$, the third network with four edges meeting at the center is best. Again, the perimeter method is best for relatively small values of $L$, when $L \leq \frac{1}{3 - 2 \sqrt{2}}$. \section{Minimizing networks in $\Re^n$.} \label{sec:higher} We show that in $\Re^n$, there are networks which minimize length plus the number of Steiner points that have $2n$ edges meeting at a point. The proof proceeds by proving the result for $n=3$ and then a more general proof applies. We also give a bound on the number of edges that can meet at a Steiner point in a network minimizing length plus number of Steiner points in $\Re^n$. Using a slightly different approach, we find a sharper upper bound for minimizing networks in $\Re^3$. \subsection{$2n$ edges can meet in $\Re^n$.} \blm \label{lm:oneSp} For $n \geq 2$, the minimizing network connecting the vertices of an $n$-dimensional cross polytope with one Steiner point connects every vertex directly to the Steiner point. \elm \bpf Consider the n dimensional cross polytope of edge length $l$. Since it has $2n$ vertices, connecting them by a tree on the perimeter has cost $l(2n-1)$. Connecting its vertices to a Steiner point in the center has cost $1 + \sqrt{2}nl$. Thus, the center network is cheaper for $ l > 1/(2n-\sqrt{2}n-1) $ and has cost greater than $ 1 + \frac{\sqrt{2}n}{2n-\sqrt{2}n-1} $. All other networks with one Steiner point may be classified by the number of vertices the Steiner point connects; call this number $t$. Since the Steiner tree portion of these networks have at least $1/\sqrt{3}$ that of their minimum spanning tree \cite{gr:rem}, they thus have cost at least $1 + l(2n-t) + \frac{1}{\sqrt{3}}tl$. Thus the center network is automatically cheaper than networks with $t < (2-\sqrt{2})/(1-1/\sqrt{3}) n $. For $t$ higher than this, there is a vertex not directly connected to the Steiner point which is closer to it than to the nearest vertex. Consider the worse case in which the $2n-t$ unnconnected vertices are mutually adjacent and form a $2n-t-1$ dimensional simplex. The projection of the Steiner network into the $2n-t$ dimensional space containing this simplex connects the origin with the $2n-t$ vertices opposite the unconnected vertices with a Steiner point. Let $x$ denote the distance between this Steiner point and the origin; our assertion that an unnconnected vertex is closer to this Steiner point than to an adjacent edge is equivalent to $ \sqrt{2} > \sqrt{ (x/\sqrt{n} + 1)^2 + (n-1)x^2/n^2 } $ or $ x < (\sqrt{1+n}-1)/\sqrt{n} $. Now, by Lemma~\ref{lm:balance}, the unit vectors of the edges meeting at the Steiner point must add to zero; and thus, so must their projections onto the line between the origin and the Steiner point. Thus the $2t-2n$ vectors giving a component of $x/\sqrt{x^2+1}$ towards the origin must balance the $2n-t$ vectors giving a component of $(1/\sqrt{n}-x)/\sqrt{x^2-2/\sqrt{n}x+1} $ away from the origin. Since for $ t > 4n/3$, $ 2t - 2n > 2n-t $, we have $ x < \sqrt{n} - \sqrt{n-1} $ which we see is always less than $(\sqrt{1+n}-1)/\sqrt{n}$. Thus, the center network is the cheapest one Steiner point network. \epf \blm A network minimizing length plus the number of Steiner points in $\Re^3$ may have six edges meeting at a point. \elm \bpf Given a set of six points on the coordinate axes in $\Re^3$ which are all distance d from the origin, consider all possible minimal networks, dividing them into cases according to the number of Steiner points they use. \noindent Case 1: No Steiner points are used. In this case all edges must connect 2 vertices, and a total of five edges are need to connect all six vertices. It is easy to compute that the shortest distance between any two vertices is $\sqrt{2}d$, thus the cost of the shortest network using no Steiner points is $5\sqrt{2}d$. \noindent Case 2: One Steiner point is used. If a Steiner point is added at the origin, then all six vertices can be connected with a cost of $6d + 1$. It is easy to compute that $6d +1 < 5\sqrt{2}d$ for $d > 0.934$. \noindent Case 3: Two or more Steiner points are used. In this case, the cost is at least two plus the length of the shortest network connecting all six points. A group of Williams students in 1989 proved that the length-minimizing network for the octahedron had four Steiner points. They also showed the eight combinatorial choices for the minimizer \cite{gg:wsp}. Here we examine each case individually. All we have to do is find a lower bound for each candidate, then show that for some $d > 0.934$, the network with one Steiner point is cheaper. Note that in these representations, $x$, $y$, and $z$ represent the axis that each segment hits at distance d from the origin. \noindent Subcase 1: Here a straightforward computation shows that length $> 5.7d$. Thus when $6d +1 < 5.7d +2$, the one Steiner point network will be cheaper. Thus for $0.934 < d < 3.333$, the one Steiner point network will be better. \noindent Subcase 2, 3, 4: The minimum distance between two points on the same axis is 2. These 3 cases are bounded below by 2d + the minimizing network connecting 4 points on the same plane forming a square with side length $\sqrt{2}d$. More specifically, length is bounded by $(4\sqrt{\frac{2}{3}} + \sqrt{2} - \frac{2} {\sqrt{6}} + 2) d$. Thus, it is cheaper to use one Steiner point when $6d + 1 < (4\sqrt{\frac{2}{3}} + \sqrt{2} - \frac{2}{\sqrt{6}} + 2) d + 2$. In other words, when $0.934 < d <\frac {1}{6-(4(0.81)+1.78)} \leq 1.04$. \noindent Subcase 5, 6: In these sub-cases, it is clear that cost is bounded by $6d$. Clearly, the one Steiner point network is cheaper. \noindent Subcase 7: This subcase is bounded by $(2 + 2 + 2\sqrt{\frac{2}{3}})d$. Thus, the Steiner network is better when $6d + 1 < (2 + 2 + 2\sqrt{\frac{2}{3}})d$. In other words, when $0.934 < d < \frac {1}{6-(5.62)} \geq 2.63$. \noindent Subcase 8: Subcase 8 is bounded by the shortest network connecting x, x, y and y + $2 \sqrt{\frac{2}{3}} d$. In other words, by $6 \sqrt{\frac{2}{3}} + \sqrt{2} - \frac{2}{\sqrt{6}}$. Thus, the 1 point network is better when $0.934 < d < \frac{1}{6-(6(0.81)+0.58)} < 1.78$. \epf We have seen that four edges of a network that minimizes length plus the number of Steiner points may meet in $\Re^{2}$, and that six edges may meet in $\Re^{3}$. We will now complete the proof that for $n \geq 2$, there is a network in $\Re^n$ that minimizes length plus the number of Steiner points and has $2n$ edges meeting at a point. \bthm $2n$ edges may meet at a Steiner point in a cost minimizing network over $\Re^{n}$ for $n \geq 4$. \ethm \bpf By Lemma~\ref{lm:oneSp}, we need only consider networks with two or more Steiner points. A network with two or more Steiner points must again have length of at least $1/\sqrt{3}$ \cite{gr:rem} that of the minimum spanning tree, and thus cost of at least $2+(2n-1)l/\sqrt{3}$. But for $l < 1/(\sqrt{2}n-\frac{1}{\sqrt{3}}(2n-1) )$ this is greater than the cost for the center network, and for $n \geq 5$, $1/(\sqrt{2}n-\frac{1}{\sqrt{3}}(2n-1) ) > 1/(2n-\sqrt{2}n-1)$. For n = 4, the cross polytope has tetrahedron as 3-faces, and any network on it must have length twice that of the shortest network on a tetrahedron, or $2 (2.445) l$, since we may project it onto a tetrahedron in four orthogonal directions. Thus any network with two or more Steiner points has cost $ \geq 2 ( 1 + 2.445 ) $, which is more expensive than the center network for $ l < 1.319 > 1/(2n-\sqrt{2}n-1) = 0.744 $. Thus for $n \geq 4$ there is a range of $l$ for which $2n$ edges meeting at a point is cost minimizing. \epf \subsection{A exponential lower bound on the number of edges that can meet at a Steiner point.} \bthm If t points are distributed on a n-sphere such that the minimum angle $\alpha$ between any two points is greater than $78.687947^{\circ}$ and if $ t > 1 / ( 1 - 2 / ( ( 1 + 1/\sqrt{3} ) \sqrt{ 2 - 2 \cos \alpha } ) )$, then there is a cost minimizing network in which at least half of them meet at a Steiner point. \ethm \bpf If the n-sphere has radius r then connecting the points through the center has cost $ 1 + r t $. Since the minimum distance between any two points is $ \sqrt{ 2 - 2 \cos \alpha } r $, connecting the points through a perimeter tree has cost at least $ \sqrt{ 2 - 2 \cos \alpha } r ( t - 1 )$. Thus the center network has lower cost for $ r > 1/( \sqrt{ 2 - 2 \cos \alpha } ( t - 1 ) - t ) $, which is positive for $ t > 4 $ and $ \alpha \geq 78.68^{\circ}$. All of other one Steiner point networks can be determined by the number of points they connect, call this number $c$. Then a one Steiner point network has minimum cost $ 1 + 1/\sqrt{3} \sqrt{2-2\cos \alpha} r c + \sqrt{2-2 \cos \alpha } r ( t-c) $, which is greater then $ 1 + r t $ for $ c < 0.5 t $ when $ \alpha \geq 78.687947^{\circ}$. Since any Steiner network has length at least $ 1/\sqrt{3} $ that of the minimum spanning tree, the cost of Steiner networks with two or more Steiner points is at least $2 + \sqrt{ 2 - 2 \cos \alpha } r ( t - 1) / \sqrt{3} $. A one Steiner point network is then cheaper for $ r < 1 / ( t - \sqrt{ 2 - 2 \cos \alpha } r ( t - 1) / \sqrt{3} ) $. Thus there is a range of $r$ for which a one Steiner point network is cost minimizing if $ 1 / ( t - \sqrt{ 2 - 2 \cos \alpha } r ( t - 1) / \sqrt{3} ) > 1/( \sqrt{ 2 - 2 \cos \alpha } ( t - 1 ) - t ) $ or $ t > 1 / ( 1 - 2 / ( ( 1 + 1/\sqrt{3} ) \sqrt{ 2 - 2 \cos \alpha } ) ) $. This is positive for $ \alpha > 78.687947^{\circ} $. \epf \bcor The number of edges which can meet in a cost minimizing network over $\Re^{n}$ grows exponentially. \ecor \bpf By \cite{erdos:maxangle}, there is a set of points of exponential cardinality on an $n$-sphere such that the angle between any pair is $>89^\circ$. \epf \subsection{An exponential upper bound on the number of edges meeting at a Steiner point.} \bthm At most \[ 2^{n} \sqrt{\pi} \frac{\Gamma( (n+1)/2 )}{\Gamma(n/2)} \] edges may meet in at a Steiner point in a cost minimizing network over $\Re^{n}$. \ethm \bpf We know that edges can not meet at a Steiner point at less than 60 degrees. Thus, there can be no more edges meeting at a Steiner point than there are 60 degree cones coming from a point. The $(n-1)$-dimensional surface area of the intersection of such a cone and the $n$-sphere is greater than its projection onto a $(n-1)$-sphere of radius $1/2 = \sin 30^\circ$. Since the surface area of the $n$-sphere is $\frac{2 \sqrt{\pi}^{n}}{\Gamma( n/2 )}$ and the volume of the $(n-1)$-sphere is $ \frac{ \sqrt{\pi}^{n-1} }{\Gamma( (n+1)/2 )} $, there can be at most \[ \bigg( \frac{2 \sqrt{\pi}^{n}}{\Gamma( n/2 )} \bigg) \bigg/ \bigg( (1/2)^{n-1} \frac{\sqrt{\pi}^{n-1}}{\Gamma( (n+1)/2 )} \bigg) = 2^{n} \sqrt{\pi} \frac{\Gamma( (n+1)/2 )}{\Gamma(n/2)} \] edges meeting at a Steiner point. \epf \bthm In $\Re^3$, at least 12 edges and at most 14 edges can come together at a point where the only restraint is that edges cannot meet at angles less than 60 degrees. \ethm \bpf At least 12 edges can meet. Edges connecting the vertices of a regular icosahedron to the center of the icosahedron have angles of $\approx 63^\circ$ between adjacent pairs. At most 14 edges can meet. Equivalently, consider the problem as one of packing $60^\circ$ cones into the unit sphere with all cones meeting at the center. If the cones do not intersect each other, the surfaces of the sphere bounded by the cones will not intersect. Clearly we can pack no more cones than the surface area of the sphere allows. First we find the surface area of a single cone portion. The surface area formula we use is $A = \int_{a}^{b} 2\pi f(x) \sqrt{1+[f'(x)]^2} dx$ and the surface is the surface of revolution obtained by rotating the curve about the x-axis. \begin{eqnarray*} A & = & \int_{\cos 30^\circ}^{1} 2\pi \sqrt{1-x^2} \sqrt{1+\frac{x^2}{1-x^2}}dx \\ & = & \int_{\cos 30^\circ}^{1} 2\pi \sqrt{1-x^2} \sqrt{\frac{1}{1-x^2}} dx \\ & = & 2\pi(x\mid_{\cos 30^\circ}^1 = 2\pi \bigg[1- \frac{\sqrt{3}}{2}\bigg] \end{eqnarray*} Since $\frac{4\pi}{2\pi[1- \frac{\sqrt{3}}{2}]}\approx14.928$, at most 14 cones can be packed with the surface area constraint. \epf \section{Acknowledgements} This paper is the work of the Geometry Group of the Williams College SMALL Undergraduate Research Project, Summer 1991, a National Science Foundation (NSF) site for Research Experiences for Undergraduates (REU). For a period of ten weeks, each of twenty--four students worked in one or two of the seven groups that comprised the project. The Geometry Group consisted of the following members: group leader Joel Foisy, Thomas Colthurst, Chris Cox, Hugh Howards, Kathryn Kollet, Holly Lowy, and Stephen Root. Professor Frank Morgan advised the group. Support for the project was provided by grants from the National Science Foundation Research Experiences for Undergraduates Program, NECUSE, Shell, and the Bronfman Science Center at Williams College. \begin{thebibliography}{Du2} \bibitem[Co1]{gg:wsp} M. Conger, M. Christian, D. Cooper, J. Goodell, Length-minimizing networks in $\Re^3$: The tetrahedron and new examples, Geometry Group, Winter Study, 1989, Advisor: F. Morgan. (Included as Appendix A of this paper) \bibitem[Co2]{co:thesis} M. A. Conger, Energy-Minimizing Networks in $\Re^n$, Honors Thesis, Williams College, 1989. \bibitem[Er]{erdos:maxangle} P. Erd\"os and Z. F\"uredi, The Greatest Angle Among $n$ Points In The $d$-Dimensional Euclidean Space, {\em Annals of Discrete Mathematics} 17(1983) 275--283. \bibitem[Gr]{gr:rem} R. L. Graham and F. K. Hwang, Remarks on Steiner minimal trees, {\em I. Bull. Inst. Math. Acad. Sinica} 4(1976) 177--182. \end{thebibliography} \end{document}