\documentstyle[11pt]{article}
\textwidth=6in
\textheight=9in
\evensidemargin=0.5in
\oddsidemargin=0.5in
\topmargin=-0.375in
\topskip=0pt
\parindent=3em
\baselineskip=24pt

\input{psfig}
\begin{document}

\Huge 

%
% Title Page
%

\vspace*{\fill}
\begin{center}
Parallel Computation\\ of \\ Steiner Minimal Trees \\
\quad \\
\quad \\
Frederick C. Harris, Jr.\\
fredh@cs.clemson.edu\\
\quad \\
Department of Computer Science\\
Clemson University\\
Clemson, SC  29634-1906
\end{center}
\vspace*{\fill}

\newpage
%
%
%
\noindent
I.  Introduction
	\begin{itemize}
	\item Original Problem 

		\vspace{0.25in}
		\begin{itemize}
		\item Given: 3 points, (A,B,C).
		\vspace{0.25in}
		\item Find: Point X that minimizes\\
		 $dist(A, X)+dist(B,X) + dist(C,X)$ 
		\vspace{0.25in}
		\item Solved independently by Fermat, \\
		Torrichelli, and Cavalieri.
		\end{itemize}	

		\begin{figure}[h]
		\vspace*{22pt}
		\centerline{\psfig{figure=chap02/fig-melzak.ps,height=3.1in}}
		\caption{\label{fig:melzak}}
		\vspace*{22pt}
		\end{figure}

	\newpage	
	\item First Expansion -- 
		\begin{itemize}
		\item 4 point problem.  
		\item Proposed by Gauss 
		\item Four Cities and Railroad lines
		\end{itemize}

	\vspace{1in}

	\item Jacob Steiner --
		\begin{itemize}
		\item 19th Century Professor
		\item University of Berlin
		\item 1 point to many 
		\item Actually the 2-D center of Mass
		\end{itemize}

	\vspace{1in}

	\item General Form of the Problem
		\begin{itemize}
		\item Paper by K\"{o}ssler and Jarn\'{i}k ('34)
		\item What is Mathematics? ('41)
		\end{itemize}

	\newpage
	\item First Algorithm
		\begin{itemize}
		\item Melzak ('61)
		\vspace{0.35in}
		\item Replace two points with a third.
		\vspace{0.35in}
		\item $T(n)=2*\left( \begin{array}{c}n\\2\end{array}
			\right)*T(n-1).$
		\vspace{0.35in}
		\item Given $n$ points and $s$ Steiner Points, 
			Sample Space is of size: 

			\vspace{0.35in}

			$ 2^{-n}\left(\begin{array}{c}n\\s+2\end{array}\right)
			\frac{(n-s-2)!}{s!} $
		\end{itemize}
	\end{itemize}

\newpage
\noindent
II.  Heuristic
	\begin{itemize}

		\vspace{0.3in}
	\item 1-Steiner Problem
		\vspace{0.3in}
		\begin{itemize}
		\item Georgakopoulos and Papadimitriou \\
		${\cal O}(n^2)$ solution
		\vspace{0.3in}
		\item At most $n-2$ Steiner Points
		\vspace{0.3in}
		\item ``greedy'' ${\cal O}(n^3)$ approach
		\end{itemize}

		\vspace{0.3in}
	\item Implementation Changes
		\vspace{0.3in}
		\begin{itemize}
		\item Their implementation is hard.
		\vspace{0.3in}
		\item Try easier, more costly methods 
		\\to see if approach is feasible.
		\end{itemize}

	\newpage
	\item Simulated Annealing \\
		start with an  $energy$ $function$, E(),\\
		to be minimized \\
		(e.g. network total distance)\\
		and a $temperature$, $T > 0$

		\vspace{1in}

		repeat
		\begin{tabbing}
		xxxxx\=yyyyy\=zzzzz\= \kill
		make small change in structure;\\
		compute $\Delta E$;\\
		if ($\Delta E < 0$)\\
		\> accept change;\\
		else\{\\
		\>r = random number in (0,1);\\
		\>if (r $< e^{-\Delta E/T}$) accept change;\\
		\>else reject change;\\
		\} \\
		\end{tabbing}
		slowly decrease temperature $T$


		\begin{figure}
		\vspace*{22pt}
		\centerline{\psfig{figure=chap02/Spann_Tree.ps,height=6.0in}}
		\caption{\label{fig:ST}Spanning Tree}
		\vspace*{22pt}
		\end{figure}

		\begin{figure}
		\vspace*{22pt}
		\centerline{\psfig{figure=chap02/SA-1.ps,height=6.0in}}
			\caption{\label{fig:SA}Simulated Annealing Solution}
		\vspace*{22pt}
		\end{figure}

		\begin{figure}
		\vspace*{22pt}
		\centerline{\psfig{figure=chap02/Exact_Solution.ps,height=6.0in}}
			\caption{\label{fig:ES}Exact Solution}
		\vspace*{22pt}
		\end{figure}


	\newpage
	\item Results 

        \begin{table}[h]
        \caption{\label{table:results}Results from 100 point problems}
	{\Large
        \begin{center}
        \begin{tabular}{|c|c|c|c|}\hline
        Exact Solution  &Spanning Tree  &Simulated Annealing &Percent
        Covered\\ \hline
        6.255463        &6.448690        &6.261797 &96.39\%     \\ \hline
        6.759661        &6.935189        &6.763495 &98.29\%     \\ \hline
        6.667217        &6.923836        &6.675194 &96.89\%     \\ \hline
        6.719102        &6.921413        &6.721283 &99.01\%     \\ \hline
        6.759659        &6.935187        &6.763493 &98.29\%     \\ \hline
        6.285690        &6.484320        &6.289342 &98.48\%     \\ \hline
        \end{tabular}
        \end{center}
	}
        \end{table}

	\vspace{1in}
	\item New Metric

	\vspace{1in}
		\[\frac{Heuristic - Spanning\_Tree}
			{Exact - Spanning\_Tree}
		\]

	\vspace{1in}
	\end{itemize}

\newpage
\noindent
III. Problem Decomposition
	
	\begin{itemize}
	\item Convex Hull
		\begin{itemize}
		\item SMT lies within this Hull
		\item Parallel Algorithm by Shamos 
		\end{itemize}

		\begin{figure}[h]
		\centerline{\psfig{figure=chap03/c_hull.ps,height=4.0in}}
		\caption{\label{fig:convex-hull}The Convex Hull for a 
			Random Set of points}
		\end{figure}

	\newpage

	\item Double Wedge
		\vspace{0.4in}
		\begin{itemize}
		\item Developed by Gilbert and Pollak
		\end{itemize}

		\vspace{1in}
		\begin{figure}[h]
		\centerline{\psfig{figure=chap03/dw.ps,width=6.0in}}
		\caption{\label{fig:double_wedge}An Illustration of
		the Double Wedge}
		\end{figure}

	\newpage

	\item Steiner Hull
		\vspace{0.3in}
		\begin{itemize}
		\item Developed by Cockayne
		\vspace{0.3in}
		\item Is smaller than the Double Wedge
		\vspace{0.3in}
		\item Removes $120^{\circ}$ triangles
		\end{itemize}

		\vspace{0.3in}

		\begin{figure}[h]
		{\Large  {\tt
		\begin{center}
		\baselineskip=12pt
		\fbox{ \parbox{6in}{
		\begin{tabbing}
		xxxxx\=yyyyy\=zzzzz\=aaaaa\= \kill
		The initial Steiner Polygon, $P_{1}$, is the Convex Hull.  \\
		Repeat \\
		\> Create Next Steiner Polygon $P_{i+1}$ from $P_{i}$ by \\
		\>\> 1) find a set of points $pqr \in {\cal S}$ such that:\\
		\> \> \>$p$ and $r$ are adjacent on $P_{i}$ \\
		\> \> \> $\angle pqr \geq 120^{\circ}$ \\
		\> \> \> $\not\!\exists$ a point from ${\cal S}$ in the
			triangle $pqr$ \\
		\> \> 2) remove the edge $pr$.  \\
		\> \> 3) add edges $pq$ and $qr$.  \\
		Until($P_{i} == P_{i+1}$)\\
		Steiner Hull = $P_{i}$
		\end{tabbing}
		}}
		\end{center}
		}}
		\caption{\label{fig:steiner_hull_alg} Steiner Hull Algorithm}
		\end{figure}

		\begin{figure}
		\centerline{\psfig{figure=chap03/s_hull.ps,height=6.0in}}
		\caption{\label{fig:steiner_hull}The Steiner Hull for a
		Random Set of 100 points}
		\end{figure}

		\begin{figure}
		\vspace*{22pt}
		\centerline{\psfig{figure=chap03/s_h.ps,height=6.0in}}
		\caption{\label{fig:steiner_hull_decomposition}The
			Steiner Hull Decomposition}
		\vspace*{22pt}
		\end{figure}
	
	\newpage
	\item Steiner Hull Extension	
		\begin{itemize}
		\vspace{0.3in}
		\item Developed by Hwang, Song, Ting and Du
		\vspace{0.3in}
		\item Removes Certain Quadrilaterals.
		\end{itemize}


		\vspace{0.5in}
		\begin{figure}[h]
		\vspace*{22pt}
		\centerline{\psfig{figure=chap03/s_h_ext.ps,width=6.0in}}
		\caption{\label{fig:steiner_hull_extension}An Illustration of
		the Steiner Hull Extension}
		\vspace*{22pt}
		\end{figure}

	\begin{figure}
	{\Large
	{\tt
	\begin{center}
	\baselineskip=12pt
	\fbox{ \parbox{6in}{
	\begin{tabbing}
	xxxxx\=yyyyy\=zzzzz\=aaaaa\=bbbbb\= \kill
	Parallel\_Steiner\_Hull() \\
	\> Input: The Convex Hull for ${\cal S}$ \\
	\> Output: The Steiner Hull for ${\cal S}$ \\
	\{ \\
	\> int i,k;\\
	\\
	\> Previous\_count = 0; \\
	\> Current\_count = Convex\_Hull.size; \\
	\> par\_for(i = 0; i < Current\_count; i++) \{\\
	\> \> Edges[i] = Convex\_Hull.edges[i];\\
	\> \} \\
	\> do \{ \\
	\> \> par\_for(i = Previous\_count; i < Current\_count; i++)\{ \\
	\> \> \> int j; \\
	\> \> \> j = i - Previous\_count; \\
	\> \> \> New\_Edges[j] = Number\_of\_new\_edges(i);\\
	\> \> \> P\_S[j] = Prefix\_Sum(j);\\
	\> \> \> for(k=0; k < New\_Edges[j].count; k++)\{ \\
	\> \> \> \> Edges[Current\_count + P\_S[j-1] + k] = \\
	\> \> \> \> \> New\_Edges[j].edges[k]; \\
	\> \> \> \} \\
	\> \> \> Update\_Links(i,Current\_count + P\_S[j-1], k);\\
	\> \> \> if(i == Current\_count -1)\{ \\
	\> \> \> \> Previous\_count = Current\_count; \\
	\> \> \> \> Current\_count = Current\_count + P\_S[j];\\
	\> \> \> \} \\
	\> \> \} \\
	\> \} while(Previous\_count != Current\_count);\\
	\}
	\end{tabbing}
	}}
	\end{center}
	}
	}

	\caption{\label{fig:parallel_steiner_hull_alg} Parallel Steiner
		Hull Algorithm}
	\end{figure}

	\end{itemize}

\newpage
\noindent
IV. Parallel Exact Computation
	\begin{itemize}
	\vspace{0.4in}
	\item GEOSTEINER
		\vspace{0.3in}
		\begin{itemize}
		\item Published in 1985	by Pawel Winter
		\vspace{0.3in}
		\item Split the process into 2 major pieces
			\begin{itemize}
			\vspace{0.3in}
			\item Generation of lists
				\begin{itemize}
				\vspace{0.3in}
				\item Q\_list
				\vspace{0.3in}
				\item T\_list
				\end{itemize}
				\vspace{0.3in}
			\item Extraction of answer from T\_list
			\end{itemize}
		\vspace{0.3in}
		\item This work has been the basis for \\
			every exact implementation since.
		\end{itemize}

		\begin{figure}
		{\large
		\input{chap04/winter.alg}
		}
		\caption{\label{fig:winter.alg} Steps 2-7 -- Winter's Algorithm}
		\end{figure}

		\begin{figure}
		{\large
		\input{chap04/seq.alg.rest}
		}
		\caption{\label{fig:main_loop} Main Loop Properly Structured}
		\end{figure}

	\newpage
	\item Parallel Building Blocks

		\begin{itemize}
		\item a\_before\_b()

		\begin{figure}[h]
		{\Large
		\input{chap04/a_before_b.c}
		}
		\caption{\label{fig:a_before_b} Function a\_before\_b()}
		\end{figure}

		\newpage
		\item mate()

		\begin{figure}[h]
		{\Large
		\input{chap04/mate.c}
		}
		\caption{\label{fig:mate} Function mate()}
		\end{figure}
		\end{itemize}

	\newpage
	\item First Approach
		\vspace{0.2in}
		\begin{itemize}
		\item Start a new slave for each new \\
		member of Q\_list
		\vspace{0.2in}
		\item Fine for small problems $<15$ points
		\vspace{0.2in}
		\item Ground to a halt rapidly for bigger problems.
		\vspace{0.2in}
		\item 100 point problem can have over 1500 members of
		Q\_list
		\vspace{0.2in}
		\item Messages
			\begin{itemize}
			\item Out of Data
			\item New Node
			\item New Tree
			\end{itemize}
		\end{itemize}
	\newpage
	\item Current Approach
		\vspace{0.2in}
		\begin{itemize}
		\item Based upon work by Quinn and Deo
		\vspace{0.05in}
		\item Master with a work Queue.
		\vspace{0.2in}
		\item Fixed number of Slaves
		\vspace{0.2in}
		\item Messages
			\begin{itemize}
			\item Out of Data
			\item New Node
			\item New Tree
			\item Change Node
			\end{itemize}
		\end{itemize}
	\end{itemize}

\newpage
\noindent
V. Extraction

	\begin{itemize}
	\item Basically just a Branch and Bound over T\_list with Enhancements
	\item Incompatibility Matrix
		\begin{itemize}
		\item Developed by Cockayne and Hewgill
		\item Entry i,j tells whether tree[i] and tree[j] can
		appear together in the answer -- greatly speeds up
		Branch and Bound.
		\end{itemize}
	\item Decomposition
		\begin{itemize}
		\item Developed by Cockayne and Hewgill
		\item Break T\_list into Bi-Connected components
		\end{itemize}
	\item Forest Management
		\begin{itemize}
		\item Developed by Cockayne and Hewgill
		\item Remove members of T\_list that cannot appear in
			the answer.
		\end{itemize}
	\end{itemize}

\newpage
\noindent
VI.  Computation Results

	\vspace{1in}
	\begin{itemize}
	\item Programs and their Results
	\vspace{1in}

	{\LARGE
	\begin{tabular}{|l|l|l|r|}\hline
	Program & Author(s) &  Points \\ \hline
	STEINER & Cockayne \& Schiller &  7 \\
		& Univ of Victoria &  \\ \hline
	STEINER72 & Boyce \& Serry & 10 \\
		& ATT Bell Labs &  \\ \hline
	STEINER73 & Boyce \& Serry & 12 \\
		&  ATT Bell Labs &  \\ \hline
	GEOSTEINER & Winter & 15 \\
		& Univ of Copenhagen &  \\ \hline
	EDSTEINER86 & Cockayne \& Hewgill & 30 \\
		& Univ of Victoria &  \\ \hline
	EDSTEINER89 & Cockayne \& Hewgill & 100 \\
		& Univ of Victoria &  \\ \hline
	PARSTEINER94 & Harris & 100 \\
		& Clemson University &  \\ \hline
	\end{tabular}
	}
	\newpage
	\item T\_list Computation time
		\vfill
		\begin{itemize}
		\item Literature only discusses averages. \\
		EDSTEINER89 209 minutes \\
		PARSTEINER94 $<20$ minutes	
		\vfill
		\item New Data \\(Computation time in Seconds)

		\begin{tabular}{|r|r|}\hline
		PARSTEINER94 & EDSTEINER89 \\ \hline
		1216	& 8597 \\ \hline
		1163	&13466	\\ \hline
		1047	&15872	\\ \hline
		1687	&17061	\\ \hline
		874	&13258	\\ \hline
		1033	&15226	\\ \hline
		1164	&12976	\\ \hline
		1109	&16697	\\ \hline
		975	&15354	\\ \hline
		554	&8650	\\ \hline
		\end{tabular}
		\end{itemize}

	\end{itemize}
\newpage
\noindent
VII. Grids

	\begin{itemize}
	\item Building Blocks
        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.2.1.ps,height=2.0in}}
                \caption{\label{fig:BB-I}Building Block ${\cal I}$}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.Y.ps,height=2.0in}}
                \caption{\label{fig:BB-Y}Building Block ${\cal Y}$}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.2.2.ps,height=2.0in}}
                \caption{\label{fig:BB-X}Building Block ${\cal X}$}
        \end{figure}

\newpage
	\item 2 x m
		\begin{itemize}
		\item Full Steiner Tree
	        \begin{figure}[h]
        	\centerline{\psfig{figure=chap06/grid.3.2.ps,height=3.0in}}
	                \caption{\label{fig:BB-S}Building Block ${\cal S}$}
       		\end{figure}
		\item Grammar Characterization
			\begin{enumerate}
			\item ${\cal X} \rightarrow {\cal S}$
			\item if No ${\cal X}$ then\\
				first ${\cal S} \rightarrow {\cal XIX}$
			\end{enumerate}
	{\Large
        \begin{table}[h]
        \caption{\label{table:grid.2.m} String Representations for 2 x m Grids}
        \begin{center}
        \begin{tabular}{|r|c|c|c|c|c|c|c|c|}\hline
         m = & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline
         String& ${\cal X}$ & ${\cal S}$ & ${\cal XIX}$ & ${\cal SIX}$ &
               ${\cal SIS}$ & ${\cal XIXIS}$ & ${\cal SIXIS}$ &
                ${\cal SISIS}$\\ \hline
        \end{tabular}
        \end{center}
        \end{table}
	}
\newpage
        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.2.4.ps,height=3.0in}}
                \caption{\label{fig:grid.2.4}SMT for a 2 x 4 Grid}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.2.5.ps,height=2.9in}}
                \caption{\label{fig:grid.2.5}SMT for a 2 x 5 Grid}
        \end{figure}


		\end{itemize}
\newpage
	\item 3 x m

        \begin{figure}[h]
        \vspace*{22pt}
        \centerline{\psfig{figure=chap06/grid.3.3.ps,height=3.0in}}
                \caption{\label{fig:grid.3.3}SMT for a 3 x 3 Grid}
        \vspace*{22pt}
        \end{figure}

        \begin{figure}[h]
        \vspace*{22pt}
        \centerline{\psfig{figure=chap06/grid.3.5.ps,height=3.0in}}
                \caption{\label{fig:grid.3.5}SMT for a 3 x 5 Grid}
        \vspace*{22pt}
        \end{figure}

\newpage

	\item 4 x m

	\begin{itemize}
	\item Building Blocks
        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.4.A.ps,height=3.0in}}
                \caption{\label{fig:grid.4.A}4 x m Pattern A}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.4.B.ps,height=3.0in}}
                \caption{\label{fig:grid.4.B}4 x m Pattern B}
        \end{figure}
\newpage
        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.4.C.ps,height=3.0in}}
                \caption{\label{fig:grid.4.C}4 x m Pattern C}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=chap06/grid.4.D.ps,height=3.0in}}
                \caption{\label{fig:grid.4.D}4 x m Pattern D}
        \end{figure}

\newpage
	\item Grammar Characterization

	\vspace{0.2in}
		4 x 5 grid is ${\cal AC}$.

	\vspace{0.2in}
		\begin{enumerate}
		\item ${\cal C} \rightarrow {\cal DB}$
		\item ${\cal B} \rightarrow {\cal C}$
		\end{enumerate}

	\vspace{1in}
	{\Large
        \begin{table}[h]
        \caption{\label{table:grid.4.m} String Representations for 4 x m Grids}
        \begin{center}
        \begin{tabular}{|r|c|c|c|c|c|c|c|}\hline
         m = & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline
         String& ${\cal AC}$ & ${\cal ADB}$ & ${\cal ADC}$ & ${\cal ADDB}$ &
               ${\cal ADDC}$ & ${\cal ADDDB}$ & ${\cal ADDDC}$ 
                \\ \hline
        \end{tabular}
        \end{center}
        \end{table}
	}
	\end{itemize}

	\end{itemize}

\newpage
\noindent
VIII. Summary

	\vfill
	\begin{itemize}
	\item Heuristic for Steiner Minimal Trees
	\vfill
	\item Accuracy Metric for Heuristics
	\vfill
	\item Parallel Steiner Hull Algorithm
	\vfill
	\item Parallel Algorithm for the generation of T\_list \\
		Computation time is decreased by an order of magnitude
	\vfill
	\item PARSTEINER94 \\
		Only the second implementation to handle 100 points
	\vfill
	\item Characterizations of SMT's for Grids \\
		(2 x m, 3 x m, 4 x m)
	\end{itemize}

\newpage
\noindent
IX. Future Work

	\begin{itemize}
	\vspace{1in}
	\item Further Parallelization
		\begin{itemize}
		\item Incompatibility Matrix Generation
		\item Branch and Bound Extraction
		\end{itemize}
	\vspace{1in}
	\item Thresholds
		\begin{itemize}
		\item Sorting
		\item Cycle Breaking
		\item Forest Management
		\end{itemize}

\newpage
	\item 1-reliable Steiner Tree Problem
        \begin{figure}[h]
        \centerline{\psfig{figure=chap08/theta1.ps,height=3.0in}}
               \caption{Theta Graph}
               \label{fig:Theta}
        \end{figure}

	\vspace{1in}
	\item Addition to existing networks
	\end{itemize}
\end{document}
