
\documentstyle[11pt]{article}
\textwidth=6.5in
\textheight=9in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin=-0.3in
\topskip=0pt
\baselineskip=12pt
\parskip=0pt 
\parindent=0em
\begin{document}
\pagenumbering{roman}
\title{DISSERTATION PROPOSAL\\
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

\addcontentsline{toc}{section}{Abstract}
\begin{abstract}
	The Steiner Problem is simply stated as follows:  Given a set
	of points $V=\{1,2,\ldots,n\}$ in the plane, construct a tree
	$T$, which contains $V$ as a subset of the vertices such that
	$T$ has minimum length.  This tree, $T$, is called the Steiner
	Minimal Tree.

	This dissertation proposal will present the problem, its
	history, and research proposals to develop parallel algorithms
	to calculate Steiner Minimal Trees.

\parskip=12pt
\parindent=0pt
{\bf keywords:} Steiner Minimal Trees, Parallel Algorithms
\end{abstract}

\newpage
\baselineskip=24pt
\addcontentsline{toc}{section}{Contents}
\tableofcontents
\newpage
\setcounter{page}{1}
\pagenumbering{arabic}

\bibliographystyle{plain}
\parindent=3em

\section{History of the Problem}

	\hspace{3em}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.  They all deduced that $P$ was inside the triangle
	formed by the given points and that the angles at $P$ are all
	$120^{\circ}$, or $P$ was one of the verticies and the angles
	at $P$ were greater than or equal to $120^{\circ}$.

	In the 19th century there was a mathematician at the University
	of Berlin by the name of Jakob Steiner.  He studied with
	interest the previous problem and then expanded it by
	attempting to find the single point whose connection to a set
	of points had the shortest possible length.

	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 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
	abandons the single point proposed by Steiner 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.

	At this point an obvious brute force method to generate the
	shortest tree for more than 3 vertices would be to calculate
	the Steiner Point (or an arc it would lie on) for every pair of
	verticies and try every combination to get the shortest tree.
	Unfortunately this does not always yield the Steiner Minimal
	Tree.  This ``method'' was all that existed until 1961 when
	Melzak developed an Algorithm to generate a Steiner Minimal
	Tree \cite{melzak61:otpos}.  Melzak's Algorithm was geometric
	in nature and based upon extensions of Figure
	\ref{fig:melzak}.
	\begin{figure}[t]
		\centering
		\vspace{3.0in}
		% now load in the PostScript image
		\special{psfile=circle2.ps}
		\caption{\label{fig:melzak}AP + CP = PX}
	\end{figure}
	Given points A, B, and C to calculate the Steiner Point to join
	them, you would first construct an equilateral triangle $(ACX)$
	based on a longest edge between two of the points $(AC)$, away
	from the third $(B)$.  A circle would then be circumscribed
	around the triangle, and a line would be constructed from the
	third point $(B)$ to the far vertex of the triangle $(X)$.  The
	location of the Steiner Point would be the intersection of this
	line $(BX)$ and the circle.

	The insight that Melzak offered was the fact that
	when constructing the Steiner Minimal Tree for more than 3
	vertices,  point X can replace points A and B and the
	algorithm can continue, thereby leaving P to be calculated
	later since B may not be known at the present time.  This is
	due to the fact that $BP + AP + CP = BP + PX$.
	This is very easy to prove since $\angle APX = \angle CPX =
	60^{\circ} $.  Using this and the law of cosines you get that
	$AP + CP = PX$.

	This algorithm was a very big step forward in the calculation
	of a Steiner Minimal Tree, yet it still required an exponential
	amount of work, since one was required to look at every subset
	of the original points.  For example, a 10 point problem has
	512 subsets of given points. Of these 45 are of size 8, with
	each having more than a million reconstruction sequences.  This
	yields what is obviously a non-polynomial time algorithm.  In
	fact Garey, et.al \cite{ggj77:tcocsmt} have shown that this
	problem is NP-Hard (NP-Complete if the distances are rounded up
	to discrete values).

\newpage
\section{Current Results}

	\hspace{3em}In 1967, just a few years after Melzak's paper,
	Cockayne\cite{cockayne67:otsp} clarified some of the details
	from Melzak's proof and proposed a new term, the Steiner
	Hull\cite{cockayne70:oteotafsmt}, which he used to decompose
	the problem.  The Steiner Hull differs from the Convex Hull,
	which is the smallest convex polygon that surrounds all the
	given points, in that it allows the polygon to dip in (not
	forcing it to be convex).  The restriction on the dips are that
	they must have an angle of at least $120^{\circ}$. When the
	same point appears more than one time in the Steiner Hull the
	verticies are divided into at least two regions.  This allows
	the problem to be decomposed into subproblems based on these
	regions, and the trees to be joined at the given point.  This
	decomposition, along with a clarified algorithm, proved to be
	the basis for the first computer program to calculate Steiner
	Minimal Trees, which appeared in \cite{cs72:cosmt}, and which
	could compute an SMT for any placement of up to $7$ vertices.

	Gilbert and Pollak made a proposition in 1968\cite{gp68:smt}
	that linked the length of the Steiner Minimal Tree to the
	length of a Minimum Spanning Tree.  At this point the Minimal
	Spanning Tree served as the upper bound on the length of the
	Steiner Minimal Tree, but they proposed a lower bound of
	$\frac{\sqrt{3}}{2}$ times the length of the Minimal Spanning
	Tree.  This proposition, which was just recently proved
	\cite{dh92:apotgpcotsr}, has been one of the primary building
	blocks for most of the heuristics that have been proposed in
	the last 20 years.

	The biggest breakthrough after Cockayne's algorithm came from
	Winter in 1985\cite{winter85:aaftspitep}  who was able to
	establish some geometric results which showed that a possible
	sub-tree could not possibly exist in the Steiner Minimal Tree.
	This enabled one to eliminate (prune out) a great many of the
	reconstruction sequences required by Melzak's algorithm.  Using
	this Winter was able to compute Steiner Minimal Trees for 15 or
	fewer vertices.  Winter's algorithm has been the basis for most
	of the enhancements in Steiner Minimal Tree algorithms since
	then.

	In 1986 two major computational breakthroughs were made.
	First, Cockayne and Hewgill\cite{ch86:ecosmtitp}  were able to
	calculate the Steiner Minimal Trees for up to 30 vertices 80\%
	of the time.  They achieved this through the use of what they
	termed an incompatibility matrix, which took the sub-trees left
	after Winter's pruning and determined whether trees $i$ and $j$
	could appear together in the Steiner Minimal Tree.  The second
	breakthrough came from Hwang and Weng\cite{hw86:hcsasmt}, who
	proposed using a hexagonal coordinate system to do all the
	calculations.  This proposal was put forth since it could
	possibly make calculation easier and the fact that all lines
	would be parallel to one of the 3 axes in the coordinate system.
	This is due to the fact that the three axis in this coordinate
	system are $120^{\circ}$ apart.

	In 1988 Hwang et.al, \cite{hstd88:adtoesmt} made another
	contribution to the field through the development of another
	decomposition theorem.  As with any NP-Hard problem, a
	theorem which allows you to partition the problem into smaller
	sub-problems is very important.  Bern and Graham have put
	together what is considered by most to be the clearest
	introductory article on the field in \cite{bg89:tsnp}.  Hwang
	and Richards have produced the most thorough survey paper in
	the field which appeared in 1992\cite{hr92:survey}.

	Most of the current results belong to Cockayne and Hewgill.  In
	1992 they expanded upon their Incompatibility Matrix and
	developed better pruning techniques that have allowed them to
	calculate Steiner Minimal Trees for up to 100 vertices 80\% of
	the time.  Their paper describing these results
	\cite{ch92:icopsmt} recently appeared in a Special Issue of
	{\it Algorithmica} which is totally devoted to the Steiner
	Problem.

\newpage
\section{Proposed Research}

	\hspace{3em}My proposal is to develop parallel algorithms for
	various portions of the Steiner Minimal Tree calculations.  The
	basic portions of the problem would have to include

		\begin{enumerate}
		\item Decomposition Algorithms -- this would obviously
		be a pre-processor stage for the next step
			\begin{itemize}
			\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{itemize}

		\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 Calculation of the Incompatibility Matrix -- 
		Cockayne and Hewgill\cite{ch86:ecosmtitp,ch92:icopsmt}.
		This step is a pre-processor step for the next stage.

		\item Combination of trees in Parallel from the list
		into a Steiner Minimal Tree.  

		\end{enumerate}

	After development of these algorithms, I will implement them,
	and hopefully be able to calculate, in parallel, Steiner
	Minimal Trees for more randomly generated points much faster, and
	with greater efficiency than is currently possible.


\newpage
\addcontentsline{toc}{section}{References}
\quad
\baselineskip=12pt
\parindent=0pt
\bibliography{/home/phd/fredh/papers/bibdir/steiner}
\end{document}
