\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. \blm In a network minimizing length plus the number of Steiner points, the sum of the unit vectors of segments meeting at a Steiner point must be $0$. \label{lm:balance} \elm \bpf It is well-known that given a vector, $v$, the derivative of $|v|$ is $\frac{v}{|v|}$. The sum of the derivatives, i.e., of the unit vectors meeting at a point must add to zero, or else we could move the Steiner point to a position that does allow the unit vectors to sum to 0, and the network would have reduced total length. \epf In particular, any Steiner point with three edges meeting must have $120^\circ$ angles between the edges. We will give some general results on networks in $\Re^2$ in sections \ref{sec:fives}, \ref{sec:free}, and \ref{sec:convex}, and categorize networks on regular polygons in $\Re^2$ minimizing length plus the number of Steiner points in section \ref{sec:regpoly}. We discuss network generalizations in $\Re^2$ in section \ref{sec:flow}, and generalizations to $\Re^n$ in sections \ref{sec:3DExamples} and \ref{sec:higher}. Finally, we discuss the standard triple bubble in section \ref{sec:triple}. \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 \blm If $90^{\circ} > a > b > 0^{\circ}$, then $\cos a + \cos b >\cos (a + \varepsilon) + \cos (b - \varepsilon)$ for $180^{\circ} > \varepsilon > 0^{\circ}$ \label{lm:2} \elm \bpf $\cos (a + \varepsilon) + \cos (b - \varepsilon) = \cos a \cos \varepsilon - \sin a \sin \varepsilon + \cos b \cos \varepsilon + \sin b \sin \varepsilon > 0$ and $\cos \varepsilon < 1$, so $\cos a \cos \varepsilon < \cos a$. Since $90^{\circ} > a > b > 0^{\circ}$, $\sin a > \sin b$, and since $180^{\circ} > \varepsilon > 0^{\circ}$, $\sin a \sin \varepsilon > \sin b \sin \varepsilon$. Thus $\cos a + \cos b > \cos a \cos \varepsilon + \cos b \cos \varepsilon > \cos a \cos \varepsilon - \sin a \sin \varepsilon + \cos b \cos \varepsilon + \sin b \sin \varepsilon > \cos a + \cos b > \cos (a + \varepsilon) + \cos (b - \varepsilon)$. \epf \begin{figure} \vspace{1.5 in} \special{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 $\frac {\| a \| + \| b \|}{\| c \|}$ will occur either at an extremum ($\beta = \gamma$ or $\beta = \alpha$) or when the derivative of $\frac {\sin (\beta + \gamma) + \sin \beta}{\sin \gamma} = 0.$ The derivative of $\frac {\sin (\beta + \gamma) + \sin \beta}{\sin \gamma} = 0$ implies $\cos (\beta + \gamma) + \cos \beta = 0$, so $-\cos (\beta + \gamma) = \cos \beta$, which implies $\cos (\frac {\pi}{2} \pm (\beta + \alpha)) = \cos \beta$. But then $\frac {\pi}{2} \pm (\beta + \alpha) = \beta$, which gives three impossible cases, and one possible one: $\beta = \frac {\pi-\gamma}{2}$. Also note that since $\alpha + \gamma + \beta = \pi, \alpha = \frac{\pi - \gamma}{2} = \beta$, there are only two cases to check. In case 1, $\alpha = \beta = \frac{\pi -\gamma}{2}$ so $$\frac {\| a \| + \| b \|}{\| c \|} = \frac{\sin (\frac {\pi}{2} + \frac{\gamma}{2}) + \sin (\frac {\pi}{2} - \frac{\gamma}{2})}{\sin \gamma} = \frac {2\cos \frac {\gamma}{2}}{\sin \gamma} = \frac{1}{\sin \frac {\gamma}{2}}.$$ In case 2, $\beta = \alpha$, and $$\frac {\| a \| + \| b \|}{\| c \|} = 1 + \frac{\sin (2\alpha)}{\sin \alpha} = 2\cos \alpha + 1.$$ For $60^{\circ} < \alpha < 180^{\circ}$ the minimum of case 1 and case 2 is case 2, where $\beta = \alpha$ and $\| a \| + \| b \| \geq \| c \|(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 \section{Minimizing networks on regular polygons} \label{sec:regpoly} In our analysis of networks minimizing the sum of the length of the network and the number of Steiner points, we looked at minimizing networks connecting the vertices of regular polygons. Since we assess a unit cost for each Steiner point, the minimizing network depends on the size of the polygon. Alternatively, we could have assumed a unit side length and variable cost for additional points. We have classified the networks on regular polygons for any side length and number of vertices. Some results from the Steiner problem are helpful in our problem. Any network minimizing length plus the number of Steiner points is the length minimizing network of its topological type, since the number of Steiner points is the same for every network of a given topological type. Also, the following lemma will remove some clearly non-minimal networks from consideration. \blm \label{lm:adjacency} A network on a regular polygon minimizing length plus the number of Steiner points will never contain non-adjacent vertices connected by an edge. \elm \bpf Assume there is a minimizing network with non-adjacent vertices connected by an edge $e$. The graph obtained by removing $e$ from the network consists of two unconnected trees. There is at least one pair of adjacent vertices that has one vertex in each of the trees, and an edge $f$ can be added between these vertices. Since the original network and the new network with $e$ removed and $f$ added have the same number of Steiner points, and the new network has shorter length, the original network was not minimizing. \epf The method of proof for the triangle, square, and pentagon will use a lemma from an undergraduate thesis by Mark A. Conger \cite{co:thesis} which states that every network connecting $n$ vertices either has $n-2$ Steiner points or is a degenerate case of a network having $n-2$ nodes. A degenerate case is a network where some of the Steiner points coincide with vertices or other Steiner points. The proof for the hexagon and larger polygons will use a more general result. \subsection{The Triangle} \begin{figure} \vspace{1.5in} \special{tri1.ps 204 0 translate} \special{tri2.ps 48 0 translate} \caption{The two possible topological types of networks minimizing length plus number of Steiner points on the equilateral triangle.} \label{fig:tri} \end{figure} On an equilateral triangle, there are two possible topological types, shown in Figure~\ref{fig:tri}: \begin{enumerate} \item The unique \cite{co:thesis} network with one Steiner point which connects with each vertex of the triangle. For this network, the cost $C(L) = 1 + \sqrt{3} L \approx 1 + 1.732 L$. \item No Steiner points and two sides of the triangle. The cost $C(L)$ of this perimeter method is $0 + 2L$, where $L$ is the side length of the triangle. This is the only possible degenerate case of the network with one Steiner point. \end{enumerate} The first possibility is best when $L \geq 2+\sqrt{3}$, and the second when $L \leq 2+\sqrt{3}$. \subsection{The Square} \begin{figure} \vspace{3.0in} \special{squ1.ps 204 0 translate} \special{squ2.ps 204 108 translate} \special{squ3.ps 48 0 translate} \special{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} On the square, there are four topological types not eliminated by Lemma~\ref{lm:adjacency}. 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 eliminated by Lemma~\ref{lm:adjacency}. 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}}$. \subsection{The Pentagon} \begin{figure} \vspace{4.5in} \special{pnt8.ps 12 216 translate} \special{pnt7.ps 132 216 translate} \special{pnt6.ps 252 216 translate} \special{pnt5.ps 12 108 translate} \special{pnt9.ps 132 108 translate} \special{pnt4.ps 252 108 translate} \special{pnt3.ps 12 0 translate} \special{pnt2.ps 132 0 translate} \special{pnt1.ps 252 0 translate} \caption{The nine possible topological types of networks minimizing length plus the number of Steiner points on the regular pentagon. Only the upper left and lower right networks are actually minimizing.} \label{fig:pnt} \end{figure} On the pentagon, there are nine topological types not eliminated by Lemma~\ref{lm:adjacency}. These are shown in Figure~\ref{fig:pnt}: \begin{enumerate} \item Three Steiner points, two each connected to two adjacent vertices and the third connected to one vertex and to the other two Steiner points. This is the length minimizing network, and has cost $C(L) = 3 + (\frac{\sin 72^\circ}{2 \sin 18^\circ} + \frac{\sqrt{3}}{2} + \frac{\sin 42^\circ} {\sin 120^\circ} + \frac{2 \sin 18^\circ}{\sin 120^\circ}) L \approx 3 + 3.891L$. \item Two Steiner points connected to each other. One has four edges meeting, and the other three. This has cost $C(L) = 2 + (\frac{2 \sqrt{3}}{3} + \frac{\sqrt{3}}{3} \frac{\sin 42^\circ} {\sin 18^\circ} + 2 \cos 36^\circ)L \approx 2 + 4.023L$. \item Two Steiner points not connected to each other, each connected to three adjacent vertices. This has cost $C(L) = 2 + (\frac{4 \sqrt{3}}{3} \sin 6^\circ + \frac{8 \sqrt{3}}{3} \sin 54^\circ) L \approx 2 + 3.978L$. \item Two Steiner points connected to each other and each to two adjacent vertices and one side of the pentagon. This has cost $C(L) = 2 + (2 + \frac{\sin 12^\circ}{\sin 120^\circ} + \frac{2 \sin 48^\circ}{\sin 120^\circ}) L \approx 2 + 3.956L$. \item Two Steiner points connected to each other, one connected to two adjacent vertices, the other to two non-adjacent vertices, and one side of the pentagon. This has cost $C(L) = 2 + (1 + \frac{2 \sqrt{3}}{3} + \frac{4 \sqrt{3}}{3} \cos 36^\circ + \sin 72^\circ - \frac{\sqrt{3}}{3} (\frac{1}{2} + \cos 36^\circ))L \approx 2 + 4.218L$. \item One Steiner point connecting four adjacent vertices and one side of the pentagon. This has cost $C(L) = 1 + (1 + 4 \cos 36^\circ ) L \approx 1 + 4.236L$. \item One Steiner point connecting two adjacent vertices and the opposite vertex of the pentagon and two sides of the pentagon. This has cost $C(L) = 1 + (2 + \frac{2 \sqrt{3}}{3} + \frac{\sqrt{3}}{3} \frac{\sin 42^\circ}{\sin 18^\circ} ) L \approx 1 + 4.405L$. \item One Steiner point connecting three adjacent vertices of the pentagon and two sides of the pentagon. This has cost $C(L) = 1 + (2 + \frac{2 \sqrt{3}}{3} \sin 6^\circ + \frac{4 \sqrt{3}}{3} \sin 54^\circ ) L \approx 1 + 3.989L$. \item The perimeter method, with no Steiner points and four sides of the pentagon. This has cost $C(L) = 4L$. \end{enumerate} The network with three Steiner points is the unique network with five vertices and three Steiner points \cite{co:thesis}. All degenerate cases which do not violate the Lemma~\ref{lm:adjacency} are listed. When the side length is larger than $L \leq 3/(4 - \frac{\sin 72^\circ}{2 \sin 18^\circ} - \frac{\sqrt{3}}{2} - \frac{\sin 42^\circ}{\sin 120^\circ} - \frac{2 \sin 18^\circ}{\sin 120^\circ}) \approx 27.56$, the minimizing network is the length minimizing network. When $L$ is smaller, the perimeter network is best. \subsection{Polygons with more sides} The length minimizing network on regular polygons with six or more vertices has been proven \cite{du:regpoly} to be the perimeter of the polygon with one edge removed. Since the perimeter uses no Steiner points, it also minimizes length plus the number of Steiner points. \section{Free Crossings} \label{sec:free} We have seen that adding a cost for Steiner points changes the configuration of the minimizing network. Jessica Polito asked whether the problem further changes when we allow two edges to cross freely without intersecting, as shown in Figure~\ref{fig:freecross}. This argument applies in $\Re^n$, and is needed to show existence of cost minimizing networks in $\Re^n$. \begin{figure} \vspace{1.5 in} \special{free.ps 126 0 translate} \caption{The two edges cross freely in the middle, without intersection.} \label{fig:freecross} \end{figure} \bthm A network minimizing length plus the number of Steiner points does not contain free crossings. \ethm \bpf Let edges $ac$ and $bd$ have a free crossing at point $p$. Since a cost minimizing network must connect all vertices, we can assume that $a$ and $b$ are connected. But then removing the free crossing edges $ac$ and $bd$ and replacing them with edges $ad$ and $bc$ will reduce the length of the network since $ad \leq ap + pd$ and $bc \leq bp + pc$ which implies $ad + bc \leq bd + ac$. \epf \section{Convexity of cones in minimizing networks} \label{sec:convex} \blm In $\Re^{2}$, if the cone connecting $n$ vertices is minimizing, the center of the cone is in the convex hull of the vertices. \elm \bpf Suppose that the center, $C$, of the cone is not in the convex hull (see Figure~\ref{fig:cone1}). \begin{figure} \vspace{1.5 in} \special{cone1.ps 126 0 translate} \caption{The center of this cone is outside the convex hull of the vertices.} \label{fig:cone1} \end{figure} Then all the segments of the cone will fall between two segments, and the angle between these two segments will be less than $180^\circ$. If this angle was $180^\circ$, $C$ would lie on a segment between two points, so $C$ would be in the convex hull. Since the whole cone is contained in an angle less than $180^\circ$, you can draw a line, $l$, through $C$, such that all the segments of the cone fall on the same side of the line. However, the network is minimizing, so the sum of the unit vectors along the segments meeting at $C$ must be 0. If all the unit vectors fall on the same side of $l$, clearly they cannot add to 0, which is a contradiction. Therefore the center of the cone is in the convex hull. \epf \bthm In $\Re^{2}$, if the cone connecting n vertices minimizes length plus the number of Steiner points, then the $n$ vertices must form a convex polygon. \ethm \bpf Suppose that the cone is cost minimizing, but that the polygon formed is not convex (see Figure~\ref{fig:cone2}). \begin{figure} \vspace{1.5 in} \special{cone2.ps 108 0 translate} \caption{The cone over a non-convex polygon.} \label{fig:cone2} \end{figure} Some vertex, $P$, will be contained in the convex hull of the n vertices. Moreover, since the center of the cone, $C$, is in the convex hull of the vertices, $P$ will be contained in a triangle formed by $C$ and two vertices, $Q$ and $Y$. If $P$ lies on $CQ$ or $CY$, then the original network is not minimizing because $CP + PQ + CQ > CP + PQ$ and $CP + PY + CY > CP + PY$, and this is a contradiction. If $CP$ is in the interior of $\triangle CQY$, to prove that the original network is not minimizing, it suffices to show that $CQ > QP$ (or $CY > YP$). Drop $CX$ perpendicular to $QY$. Since $\triangle CPQ$ is in $\triangle QXC$ ($\triangle XYC$) with two vertices, $C$, $Q$ ($C$, $Y$), in common, $\angle QPC \geq \angle QXC$ ($\angle YPC \geq \angle YXC$). Since $\angle QXC$ ($\angle YXC$) is a right angle, $CQ$ ($CY$) must be the longest side of the triangle, so $QC > QP$ ($YC > YP$). Thus, replacing $CQ$ with $CP$ ($CY$ with $CP$) results in a shorter network, which is a contradiction. \epf \section{Flow Dependent Networks} \label{sec:flow} \subsection{Variable Flow Demands: Minimal Gilbert Networks} The problem of finding networks which minimize a cost based on total length plus the number of Steiner points is simply a generalization of the classical Steiner problem, which is the limiting case for the new problem when either length approaches infinity or cost of Steiner points approaches zero. There are, of course, many other ways to generalize the problem. One that has been studied is the problem of finding minimal networks when each edge is assigned a cost based both on length and a variable flow rate. In 1967 Gilbert \cite{gi:ccm} first asked how a set of points could most efficiently be connected if a flow demand were assigned for each pair of points and a cost assigned to each arc in the network as a function of the flow demands of all points which may be connected by a path through the arc. Such a broad generalization indeed proved difficult, and little work has been done on solving specific cases. In 1985 Trietsch and Handler \cite{tr:gpc} worked on generalizing the Gilbert-Pollack conjecture, which claims that every network with Steiner points is at least $\frac{\sqrt{3}}{2}$ times the minimal spanning tree, for these flow dependent networks, which they named Gilbert Minimal Networks. They proved that the generalized conjecture is equivalent to the original conjecture for the Minimal Gilbert Network over three points, approaching the ratio of $\frac{\sqrt{3}}{2}$ when all three flow demands become equal. They then conjectured that the Gilbert-Pollack conjecture of regular Steiner trees was equivalent to that of Minimal Gilbert Networks connecting any number of points. This was disproved within a year by Du and Hwang \cite{du:cth} who gave a counterexample using the vertices of a square. They also provided a shorter geometric proof of the case involving three points. Specific cases, in particular regular polygons, can be be considered in variable flow networks if a somewhat less general approach is used. One simplification is to assign a single flow demand to entire classes of edges, based solely on the number of Steiner points they use rather than which vertices they connect. Three cases are considered and minimal networks are conjectured for the square and pentagon. In these cases the minimal network for the vertices of a given polygon will vary according to the relative values of the constants. \subsection{Constant Flow Demand} Case 1: Let edges connecting vertices along the perimeter be given a cost of $k_{1}$ per unit length and let all other edges be given a cost of $k_{2}$. For the vertices of a square, it is clear that as $k_{1}\longrightarrow k_{2}$ the problem reduces to the original Steiner problem. For $\frac{k_{2}}{k_{1}}$ less than approximately 1.1 the solution is the overall length minimizing network with two Steiner points. Otherwise the perimeter network is minimal. Similarly for the vertices of a regular pentagon, as $\frac{k_{2}}{k_{1}}\longrightarrow 1$ and as $\frac{k_{2}}{k_{1}}\longrightarrow \infty$ the minimal networks are respectively the Steiner minimal network and the minimal spanning tree. The only other possible minimal cases are those with one or two perimeter edges, and these can be eliminated by straightforward calculations. The two minimal types are delineated at $\frac{k_{2}}{k_{1}}\approx 1.03$. \vspace{.5cm} Case 2: Let edges touching vertices at one or both ends be given a cost of $k_{1}$ per unit length and let all other edges be given a cost of $k_{2}$. This problem is now distinguished from Case 1 and the main problem by the fact that moveable Steiner points may now connect edges of different cost per unit length. The requirement that edges meet at 120 $\deg$ no longer holds, but by a similar argument it can be proven that when two edges of unit cost $k_{1}$ meet an edge of cost $k_{2}$ the angle $\theta$ between the two edges of cost $k_{1}$ is given by the formula $\frac{k_{2}}{k_{1}}=\frac{1}{2\cos{\frac{\theta}{2}}}$. As a result the minimal network varies continuously as $\frac{k_{2}}{k_{1}}$ changes. In the square, for example, as $\frac{k_{2}}{k_{1}}$ goes from 1 to $\sqrt{2}$ the minimal network varies from the Steiner minimal tree to a network with a single Steiner point at the center, as the center edge gradually shortens and then disappears. For the pentagon, however, the problem becomes more difficult. The minimal network of each topological type varies as a complicated function of $k_{1}$ and $k_{2}$. \vspace{.5cm} Case 3: Let each edge be given a cost $k_{i}$ where $i$ is the degree that the edge is removed from the perimeter, that is, perimeter edges are given a cost $k_{0}$, edges touching one vertex are given a cost $k_{1}$, etc. In fact for many topological types the solution is identical to Case 2. Even for the square, the solution is difficult to calculate. It can be seen that three topological types can be minimal for the square by setting $k_{0}=1$ and graphing the minimal network as $k_{1}$ and $k_{2}$ vary, taking the minimum of the equations for all four types. A similar method could be used for the pentagon, although it is computationally difficult. In all three cases above, the minimal network for the vertices of an n-gon for $n=6$ or greater will be simply the minimal spanning tree on the perimeter, if the assumption is made that $k_{i} 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$. \begin{figure} \vspace{1.5in} \special{nost1.ps} \special{nost2.ps 252 0 translate} \caption{No Steiner Points Used. The length of the network on the right is $5 \protect\sqrt{2} d$.} \label{fig:0sp} \end{figure} \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: \begin{figure} \vspace{2.0in} \special{subcase1b.ps} \special{subcase1a.ps 216 0 translate} \caption{Subcase 1. The network at right has length three times that of the piece of the network component on the left, which has length $> 1.93d$.} \label{fig:subcase1} \end{figure} 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: \begin{figure} \vspace{1.5in} \special{subcase2.ps 107.5 0 translate} \caption{Subcases 2. The portion of the network in the dotted circle has length at least $2d$.} \label{fig:subcase2} \end{figure} \begin{figure} \vspace{1in} \special{subcase3.ps 77 0 translate} \caption{Subcases 3. The $y$-legs have length $\geq 2d$ and the remaining portion of the network is the minimizing network on a square with side length $\protect\sqrt{2}d$.} \label{fig:subcase3} \end{figure} \begin{figure} \vspace{1in} \special{subcase4.ps 77 0 translate} \caption{Subcases 4. The $z$-legs have length $\geq 2d$ and the remaining portion of the network is the minimizing network on a square with side length $\protect\sqrt{2}d$.} \label{fig:subcase4} \end{figure} 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: \begin{figure} \vspace{1.5in} \special{subcase5.ps 127.5 0 translate} \caption{Subcases 5. The length of the portion of the network in each dotted circle is $\geq 2d$.} \label{fig:subcase5} \end{figure} \begin{figure} \vspace{1.25in} \special{subcase6.ps 40 0 translate} \caption{Subcases 6. The length of the portion of the network in each dotted circle is $\geq 2d$.} \label{fig:subcase6} \end{figure} In these sub-cases, it is clear that cost is bounded by $6d$. Clearly, the one Steiner point network is cheaper. \noindent Subcase 7: \begin{figure} \vspace{1.5in} \special{subcase7.ps 63.5 0 translate} \caption{Subcase 7. The parts of the network in the dotted ellipses each have length $\geq 2d$, and the parts of the network in the dotted circles each have length $\geq \protect\sqrt{\frac{2}{3}}$.} \label{fig:subcase7} \end{figure} 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: \begin{figure} \vspace{1.0in} \special{subcase8.ps 96 0 translate} \caption{Subcase 8. The parts of the network in the dotted circles each have length $\geq \protect\sqrt{\frac{2}{3}} d$, and the parts in the large ellipse have length $\geq (4 \protect\sqrt{\frac{2}{3}} + \protect\sqrt{2} - \frac{2}{\protect\sqrt{6}}) d$.} \label{fig:subcase8} \end{figure} 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 size 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{Parameterization of Triple Bubbles} \label{sec:triple} As a first step towards proving the existence of a standard triple bubble, we sought a three variable parameterization of such. The first step in this endeavor was the parameterization of the vertex graph of the triple bubble: the graph formed by replacing the arcs in the bubble by striaght lines. If we consider such a graph for a general n-bubble configuration (with $n>2$), we see that each junction separates three different regions, or, equivalently that no two edges connect the same two junctions. This follows from Lemma 2.6 of \cite{joel:thesis} and the fact that perimeter minimizing configurations cannot be disconnected. By Euler's Formula, $V-E+F = 1$ and from the above, $E=3V/2$, so $V=2F-2$ or since $F=n$, $V=2(n-1)$. Now, the vertex graph can be parameterized by one scale perimeter which specifies the length of some edge and by $2V$ angle parameters -- the third angle at each vertex is determined by the other two. From this we may eliminate one variable for each face, since the interior angles of a face are constrained to sum to some multiple of $\pi$, for a total of $1 + 2 * 2(n-1) - n = 3n - 3 $ variables. Onto this vertex graph we must fit the circular arcs. If we allow one variable to specify the angle between a given arc and its edge, then the rest of the arcs are determined in their placement by the constraint that they must meet at angles of $120^{\circ}$. In fact, they are over-determined: if we go around a closed circuit in the vertex graph, we find a arc whose placement is determined from both sides. Thus we must subtract off a parameter for each independent close circuit, which is just $n$ variables, which gives us a grand total of $ 2n-2 $ variables. To reduce this total down to the desired $n$ variables, we must use pressure arguments. There are $V-1$ independent paths for which the sum of oriented curivatures must be zero, one around each vertex except one. This, however, leads to a dilemma: each of these independent paths cannot possibly give us independent pressure equations, since this would leave us with $ 2n-2 - ( 2n-2 - 1 ) = 1 $ variable, which is ludicrious. It might be interesting to study how these pressure equations are interrelated. The above line of attack was completed for the standard triple bubble, for which only one variable needs to be eliminated by pressure arguments. All of the variables in Figure 1 are determined by the edge length A and the angles $\alpha$ and $\Delta$. The only nontrivial calculation is for the angle $\beta$, which is \[ \beta = -2 \cot^{-1}\bigg( \frac{\sin \alpha - 30^{\circ}}{\sin \alpha} \frac{\sin 60^{\circ} - \Delta}{\sin \Delta} - \frac{\sin 30^{\circ} - \Delta}{\sin \Delta} - \sqrt{3}/2 \bigg) \] \vspace{0.5cm} At his talk this summer at SMALL, John Sullivan suggested an extremely elegant method of showing the existence of triple bubbles for any three given areas. Since the existence of a standard triple bubble with three equal areas is known \cite{joel:thesis}, we may stereographically project it onto a unit sphere. It can be shown that translating the triple bubble on the sphere and then projecting it back onto the plane gives a locally perimeter-minimizing configuration. Since we have two parameters of translation on the sphere, a triple bubble with any two ratios of areas can be achieved. This method can be generalized to show the existence of a standard (n+1)-bubble in $\Re^n$. \section{Open Questions} Some problems for further research are given below. \begin{enumerate} \item What is the maximum number of edges that can meet in a minimizing Steiner network in $R^3$? (We know this number is at least 6 and at most 14). \item What is the structure of minimizing networks with cost based on the flow of traffic on edges? This problem was introduced in \cite{gi:ccm}. Further work on the problem was done in \cite{tr:gpc} and \cite{du:cth}. \item What is the structure of minimizing networks in hyperbolic space? \item What is the structure of minimizing directed networks? Length minimizing directed networks are treated in \cite{al:sdn}. \item Can flow (see \cite{lawlor:flow}) be used to prove that the minimal spanning tree of regular polygons with 6 or greater sides is minimizing? \item What is the structure of minimizing networks where cost is based on the number of Steiner points? For example, if the cost of each additional Steiner point grows exponentially. \end{enumerate} \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[Al]{al:sdn} M. Alfaro, Shortest Directed Networks in $\Re^2$, Honors Thesis, Williams College, 1990. \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[Du1]{du:cth} D. Z. Du and F. K. Hwang, On a Conjecture of Trietsch and Handler on the Flow-Dependent Steiner Ratio, {\em Networks} 16(1986) 47--50. \bibitem[Du2]{du:regpoly} D. Z. Du, F. K. Hwang, and J. F. Weng, Steiner Minimal Trees for Regular Polygons, {\em Discrete and Computational Geometry} 2(1987) 65--84. \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[Fo]{joel:thesis} J. Foisy, Soap Bubble Clusters in $\Re^2$ and $\Re^3$, Honors Thesis, Williams College, 1991. \bibitem[Gi1]{gi:ccm} E. N. Gilbert, Minimum Cost Communication Networks, {\em Bell System Tech. J.} 46(1967) 2209--2227. (This paper presents Gilbert's presentation of the flow-dependent arc question.) \bibitem[Gi2]{gi:smt} E. N. Gilbert and H. O. Pollak, Steiner Minimal Trees, {\em SIAM J. Appl. Math.} 16(1968) 1--29. \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. \bibitem[La]{lawlor:flow} G. Lawlor and F. Morgan, Minimizing Cones and Networks: Immiscible Fluids, Norms, and Calibrations, preprint (1991). \bibitem[Tr]{tr:gpc} D. Trietsch and G. Handler, The Gilbert and Pollak Conjecture --- A Generalization, {\em Networks} 15(1985) 365--380. \end{thebibliography} \appendix \section{Length Minimizing Networks in $\Re^3$: \newline The Tetrahedron and New Examples} \begin{center} M.~Conger \quad M.~Christian \\ D.~Cooper \quad J.~Goodell \\ Winter Study 1989 \end{center} \end{document}