
\documentstyle[12pt]{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

{\bf Committee Members:} S.T. Hedetniemi, R.C. Laskar, B.A. Malloy, R.P. Pargas
\end{abstract}

\newpage
\setcounter{page}{1}
\pagenumbering{arabic}

\bibliographystyle{plain}
\Huge
	%\vspace*{\fill}
	\begin{enumerate}
	\item History of the Problem
		\LARGE
		\begin{itemize}
		\item {\bf The Problem posed in the 17th century:}  \\
		Find the point $P$ that minimizes the sum of the
		distances from $P$ to each of three given points.

		\vspace{1.0in}

		\item {\bf Solutions} to this problem were derived
		independently by Fermat, Torricelli, and Cavalieri.

	\vspace*{\fill}
\newpage

		\item {\bf Expansion of the Problem:} \\
		Jakob Steiner -- attempted to find the single point
		whose connection to a set of points had the shortest
		possible length.

		\vspace{1.0in}

		\item {\bf General Form:}
			\begin{enumerate}
			\item Appeared in a paper by K\"{o}ssler and
			Jarn\'{i}k in 1934 \cite{jk34:omgodb},

			\vspace{1.0in}

			\item It did not become popular until the book,
			{\it What is Mathematics}, by Courant and
			Robbins \cite{cr41:wim}, appeared in 1941.
			\end{enumerate}
\newpage
		\item {\bf The First Algorithm (`61)-- Melzak\cite{melzak61:otpos}} \\
			Melzak's Algorithm was geometric in nature.
			\vfill
	  		\begin{enumerate} 
			\item First construct an equilateral triangle
			$(ACX)$ based on a longest edge between two of
			the points $(AC)$, away from the third $(B)$.
			\vfill
			\item A circle would then be circumscribed
			around the triangle,
			\vfill
			\item A line would be drawn from the third
			point $(B)$ to the far vertex of the triangle
			$(X)$.

			\vfill

			\item The location of the Steiner Point would
			be the intersection of this line $(BX)$ and the
			circle.

			\end{enumerate}

		\end{itemize}

\newpage
\Huge
	\item {Current Results}
	\LARGE

		\begin{itemize}
		\item 1967 -- Cockayne cleaned up Melzak's Proof

			\vfill

		\item 1968 -- Gilbert-Pollak conjecture\cite{gp68:smt}
			\begin{enumerate}
			\vfill
			\item Upper Bound -- Minimal Spanning Tree 
			\vfill
			\item Lower Bound -- $\frac{\sqrt{3}}{2} * MST$ \\
				Just proved in \cite{dh92:apotgpcotsr}
			\end{enumerate}
			\vfill
			This has been the basis of most heuristics to
			calculate the Steiner Minimal Tree.
			\vfill
		\item 1970 -- Cockayne proposed the Steiner
		Hull\cite{cockayne70:oteotafsmt}

			\vfill Basis of decomposition for this problem
		\end{itemize}

\newpage
\Huge
		\item Computational Results
		\LARGE
			\begin{itemize}
			\item 1972 Cockayne and Schiller \cite{cs72:cosmt}\\
				 7points all the time.
			\vfill
			\item 1973 Boyce and Seery (Bell Labs) \\
				10 then 12 points all the time.\\
				They cleaned up Cockayne's work.

			\vfill
			\item 1985 Winter \cite{winter85:aaftspitep} \\
				15 points -- all the time.\\
				Projected 30 could be done

			\vfill
			\item 1986 Cockayne and Hewgill \cite{ch86:ecosmtitp} \\
				30 points (80\% of the time)
			\vfill
			\item 1992 Cockayne and Hewgill \cite{ch92:icopsmt} \\
				100 points (80\% of the time)
			\vfill
			\end{itemize}
\newpage
	\item{Proposed Research}

		\begin{itemize}
		\item Algorithm Development
		\vfill

			\begin{enumerate}
			\item Decomposition Algorithms 
				\vfill
				\begin{enumerate}
				\item Gilbert and Pollak -- Double
				Wedge\cite{gp68:smt} (subset of the next
				decomposition)
				\vfill
				\item Cockayne and Hewgill -- Steiner
				Hull\cite{cockayne70:oteotafsmt} 
	
				\vfill
				\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}
	
				\vfill
			\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.

			\vfill
\newpage

			\item Combination of partial-trees into a Steiner
				Minimal Tree.

				\vfill
				\begin{enumerate}
				\item Calculation of the Incompatibility Matrix -- 
				Cockayne and Hewgill\cite{ch86:ecosmtitp,ch92:icopsmt}.
				\vfill

				\item Further decomposition based on the partial-trees
				\cite{ch86:ecosmtitp}
				\end{enumerate}
			\end{enumerate}

			\vfill

		\item Implementation
			Calculation in parallel of Steiner Minimal
			Trees for more randomly generated points much
			faster, and with greater efficiency than is
			currently possible.
\vfill
		\end{itemize}
	\end{enumerate}


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