
\documentstyle{article}
\textwidth=6.5in
\textheight=9in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin=-0.3in
\topskip=0pt
\baselineskip=12pt
\parskip=5pt 
\parindent=0em
\begin{document}
\bibliographystyle{plain}
%\pagenumbering{roman}
%\title{
%Parallel Algorithms\\
%for the Calculation of\\
%Steiner Minimal Trees in the Plane}
%\author{ Frederick C. Harris, Jr.\\
%\\
%Department of Computer Science \\
%Clemson University 
%}
%\date{\quad}
%\maketitle




	The Steiner Problem is probably one of the oldest
	optimization problems in mathematics, and consequently it has
	been worked on by most of the leading mathematicians in
	history.  In the mid-17th century a simple problem was posed:
	Find the point $P$ that minimizes the sum of the distances from
	$P$ to each of three given points.  Solutions to this problem
	were derived independently by Fermat, Torricelli, and
	Cavalieri.  

	The general form of this optimization problem appeared in a
	paper by K\"{o}ssler and Jarn\'{i}k in 1934 \cite{jk34:omgodb},
	but it did not become popular until the book, {\it What is
	Mathematics}, by Courant and Robbins\cite{cr41:wim}, appeared
	in 1941. Courant and Robbins linked the name Steiner, a 19th
	century mathematician, with the general form of the problem
	proposed by K\"{o}ssler and Jarn\'{i}k, and it stuck.  The
	general form of the problem goes beyond the 3 point initial 
	problem and allows multiple points to be added, each of
	which is called a Steiner Point.  Therefore, instead of
	creating a star, a simple tree is created and the distance to
	be minimized is the length of the tree.

	Melzak developed the first algorithm, which was geometric in
	nature, to generate a Steiner Minimal Tree in 1961
	\cite{melzak61:otpos}. The insight that Melzak offered was the
	fact that when constructing the Steiner Minimal Tree for more
	than 3 vertices,  an n point problem can be replaced by a
	finite number of problems of size n-1. This yields what is
	obviously a non-polynomial time algorithm.  In fact Garey,
	et.al \cite{ggj77:tcocsmt} have shown that this problem,
	which is NP-Hard, is NP-Complete if the distances are rounded up to
	discrete values.

	Melzak's algorithm has been the foundation for computer programs by
	various authors to calculate Steiner Minimal Trees.  Table
	\ref{table:steiner-programs} presents some of these programs
	and their results.
	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|l|l|r|}\hline
	Authors												& Location					& \# pts.\\
	\hline
	Cockayne \& Schiller \cite{cs72:cosmt}		& Univ. of Victoria		& 7 \\ 
	Boyce \& Seery\cite{bs75:aivocspsftmnp}	& Bell Labs. 				& 10 \\
	Winter \cite{winter85:aaftspitep} 			& Univ. of Copenhagen	& 15 \\ 
	Cockayne \& Hewgill \cite{ch86:ecosmtitp}	& Univ. of Victoria		& 30 \\
	Cockayne \& Hewgill \cite{ch92:icopsmt}	& Univ. of Victoria		& 100 \\
	\hline
	\end{tabular}
	\end{center}
	\caption{\label{table:steiner-programs}Steiner Minimal Tree Results}
	\end{table}


	In order to develop a parallel algorithm to calculate Steiner Minimal
	Trees, one would have to look at various portions of the problem, which
	would have to include:

		\begin{enumerate}
		\item Decomposition Algorithms.
			\begin{enumerate}
			\item Gilbert and Pollak -- Double
			Wedge\cite{gp68:smt} (subset of the next
			decomposition)

			\item Cockayne and Hewgill -- Steiner
			Hull\cite{cockayne70:oteotafsmt} 

			\item Hwang et.al\cite{hstd88:adtoesmt} --
			allows decomposition of the Steiner Hull into
			smaller polygons whose Steiner Minimal Trees
			are joined by an edge.

			\end{enumerate}

		\item Construction of small partial trees into a list
		-- Winter\cite{winter85:aaftspitep} -- Using the
		geometric properties proposed by Winter and developing
		a parallel algorithm to calculate the list of sub-trees
		that are the foundation to the Steiner Minimal Tree.

		\item Combination of partial-trees into a Steiner Minimal Tree.
			\begin{enumerate}
			\item Calculation of the Incompatibility Matrix
			-- Cockayne and Hewgill
			\cite{ch86:ecosmtitp,ch92:icopsmt}.
			\item Further decomposition based on the
			partial-trees \cite{ch86:ecosmtitp} 
			\end{enumerate}

		\end{enumerate}

	Other Problems:
		\begin{itemize}
		\item How sensitive is the topology (structure) of a
		SMT to small changes in the locations of the original
		points.  
		\item The Gilbert-Pollak conjecture \cite{gp68:smt},
		$SMT \geq \frac{\sqrt{3}}{2} * MST$, conjecture has
		been proven for any graph \cite{dh92:apotgpcotsr}, but
		is there a tighter bound for certain classifications of
		graphs.  
		\item How to attach new nodes to an already existing 
		network with minimal distance.
		\end{itemize}

%\parskip=12pt
%\parindent=0pt
%{\bf keywords:} Steiner Minimal Trees, Parallel Algorithms
%
%\newpage
%\cite{jk34:omgodb}
%\cite{cr41:wim}
%\cite{melzak61:otpos}
%\cite{cockayne67:otsp}
%\cite{cockayne67:otsp}
%\cite{cockayne70:oteotafsmt}
%\cite{cs72:cosmt}
%\cite{bs75:aivocspsftmnp}
%\cite{ggj77:tcocsmt}
%\cite{winter85:aaftspitep}
%\cite{hw86:hcsasmt}
%\cite{ch86:ecosmtitp}
%\cite{hstd88:adtoesmt}
%\cite{bg89:tsnp}
%\cite{dh92:apotgpcotsr}
%\cite{ch92:icopsmt}
%\cite{hr92:survey}
%
%\newpage
\addcontentsline{toc}{section}{References}
\quad
\baselineskip=12pt
\parindent=0pt
\bibliography{/home/phd/fredh/papers/bibdir/steiner}
\end{document}
