\section{Motivation and Literature}

	After the early work by Melzak~\cite{melzak61:otpos}, many
	people began to work on the Steiner Minimal Tree problem.  The
	first major effort was to find some kind of geometric bound for
	the problem.  In 1968 Gilbert and Pollak~\cite{gp68:smt} showed
	that the SMT for a set of points, ${\cal S}$, must lie within
	the Convex Hull of ${\cal S}$.  This bound has since served as
	the starting point for every  bounds enhancement for SMT's.

	As a brief review, the Convex Hull is defined as follows: Given
	a set of points ${\cal S}$ in the plane, the Convex Hull is the
	convex polygon of smallest area containing all the points of
	${\cal S}$.  A polygon is defined to be convex if a line
	segment connecting any two points inside the polygon lies
	entirely within the polygon. An example of the Convex Hull for
	a set of 100 randomly generated points is shown in
	Figure~\ref{fig:convex-hull}.

	\begin{figure}
	\vspace*{22pt}
	\centerline{\psfig{figure=chap03/c_hull.ps,height=6.0in}}
	\caption{\label{fig:convex-hull}The Convex Hull for a random set of 
		points.}
	\vspace*{22pt}
	\end{figure}


	Shamos in his PhD thesis~\cite{shamos:phd} proposed a Divide
	and Conquer Algorithm which has served as the basis for many
	parallel algorithms calculating the Convex Hull.  One of the
	first such approaches appeared in the PhD thesis by
	Chow~\cite{chow:phd}.  This approach was refined and made to
	run in optimal ${\cal O}(log \ n)$ time by Aggarwal
	et.al.~\cite{acgoy88:pcg}, and Attalah and
	Goodrich~\cite{ag88:pafsfotcp}.

	The next major work on the SMT problem was in the area of
	problem decomposition.  As with any non-polynomial algorithm,
	the most important theorems are those that say ``If property
	${\cal P}$ exists, then the problem may be split into the
	following sub-problems.''  For the Steiner Minimal Tree Problem
	property ${\cal P}$ will probably be geometric in nature.
	Unfortunately, decomposition theorems have been few and far
	between for the SMT problem.  In fact, at this writing there
	have been only three such theorems.

	\vspace*{11pt}
	\subsection{The Double Wedge Theorem}

		The first decomposition theorem, known as the Double
		Wedge Theorem,  was proposed by Gilbert and
		Pollak~\cite{gp68:smt}.  This is illustrated in
		Figure~\ref{fig:double_wedge} and can be summarized
		quite simply as follows:  If two lines intersect at
		point ${\cal X}$ and meet at $120^{\circ}$, they split
		the plane into two $120^{\circ}$ wedges and two
		$60^{\circ}$ wedges.  If $R_{1}$ and $R_{2}$ denote the
		two $60^{\circ}$ wedges, and all the points of ${\cal
		S}$ are contained in $R_{1} \bigcup R_{2}$, then the
		problem can be decomposed.  There are two cases to be
		considered.
		In case 1 ${\cal X}$ is not a point in ${\cal S}$;
		therefore, the Steiner Minimal Tree for ${\cal S}$ is the SMT
		for $R_{1}$, the SMT for $R_{2}$, and the shortest edge
		connecting the two trees.
		In case 2 ${\cal X}$ is a point in ${\cal S}$;
		therefore,  the Steiner Minimal Tree for ${\cal S}$ is the 
		SMT for
		$R_{1}$ and the SMT for $R_{2}$. Since ${\cal X}$ is in
		both $R_{1}$ and $R_{2}$ the two trees are connected.

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

	%\vspace*{11pt}
	\subsection{The Steiner Hull}
	
		The next decomposition theorem is due to
		Cockayne~\cite{cockayne70:oteotafsmt} and is based upon
		what he termed the {\it Steiner Hull}.  The Steiner
		Hull is defined as follows:  let $P_{1}$ be the convex
		Hull. $P_{i+1}$ is constructed from $P_{i}$ by finding
		an edge ($p,r$) of $P_{i}$ that has a vertex ($q$)
		near it such that $\angle pqr \geq 120^{\circ}$ and
		there is not a vertex inside the triangle $pqr$.  The
		final polygon, $P_{i}$, that can be created in such a
		was is called the Steiner Hull.  The Algorithm for this
		construction is shown in
		Figure~\ref{fig:steiner_hull_alg}.  The Steiner Hull
		for the 100 points shown in
		Figure~\ref{fig:convex-hull} is given in
		Figure~\ref{fig:steiner_hull}.

\newpage

		\hspace{1in}

		\begin{figure}
		\vspace*{3in}
		{ \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}The Steiner Hull algorithm.}
		%\vspace*{\fill}
		\end{figure}
	
	
		\begin{figure}
		\vspace*{22pt}
		\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.}
		\vspace*{22pt}
		\end{figure}

\textheight=10in

\newpage
		After defining the Steiner Hull, Cockayne showed that
		the SMT for ${\cal S}$ must lie within the Steiner Hull
		of ${\cal S}$.  This presents us with the following
		decomposition: The Steiner Hull can be thought of as an
		ordered sequence of points, $\{p_{1}, p_{2}, \ldots,
		p_{n}\}$, where the hull is defined by the sequence of
		line segments, $\{p_{1}p_{2}, p_{2}p_{3}, \ldots,
		p_{n}p_{1}\}$.  If there exists a point $p_{i}$ that
		occurs twice in the Steiner Hull, then the problem can
		be decomposed at point $p_{i}$. If a Steiner Hull
		contains such a point, then the Steiner Hull is
		referred to as {\it degenerate}.  This decomposition is
		accomplished by showing that the Steiner Hull splits
		${\cal S}$ into two contained subsets, $R_{1}$ and
		$R_{2}$, where $R_{1}$ is the set of points contained
		in the Steiner Hull from the first time $p_{i}$
		appears until the last time $p_{i}$ appears, and
		$R_{2}$ is the set of points contained in the Steiner
		Hull from the last time $p_{i}$ appears until the
		first time $p_{i}$ appears. With this decomposition
		it can be shown that ${\cal S} = R_{1} \bigcup R_{2}$,
		and the SMT for S is the union of the SMT for $R_{1}$
		and the SMT for $R_{2}$.  This decomposition is
		illustrated in
		Figure~\ref{fig:steiner_hull_decomposition}.  Cockayne
		also proved that the Steiner Hull decomposition includes
		every decomposition possible with the Double Wedge
		Theorem.

		In their work on 100 point problems, Cockayne and
		Hewgill~\cite{ch92:icopsmt} mention that approximately
		$15\%$ of the randomly generated 100 point problems
		have degenerate Steiner Hull's. The Steiner Hull shown
		in Figure~\ref{fig:steiner_hull} is not degenerate,
		while that in
		Figure~\ref{fig:steiner_hull_decomposition} is.

		\begin{figure}
		\vspace*{22pt}
		\centerline{\psfig{figure=chap03/s_h.ps,height=6.0in}}
		\caption{\label{fig:steiner_hull_decomposition}An
			illustration of the Steiner Hull decomposition.}
		\vspace*{22pt}
		\end{figure}

	\vspace*{11pt}
	\subsection{The Steiner Hull Extension}

		The final decomposition belongs to Hwang, Song,
		Ting and Du~\cite{hstd88:adtoesmt}.  They proposed an
		extension to the Steiner Hull as defined by Cockayne.
		Their extension is as follows:

		\noindent
		If there exist four points $a,b,c,d$ on a Steiner 
		Hull such that:

		1. $a,b,c,d$ form a convex quadrilateral,

		2. there does not exist a point from 
			${\cal S}$ in the quadrilateral $(a,b,c,d)$,

		3. $\angle a \geq 120^{\circ}$ and 
				$\angle b \geq 120^{\circ}$,

		4. the two diagonals (ac) and (bd) meet at O, and
				$\angle bOa \geq \angle a + \angle b -
				150^{\circ}$,

		\noindent
		then the SMT for ${\cal S}$ is the union of the SMT's for
		$R_{1}$ and $R_{2}$ and the edge $ab$ where $R_{1}$ is
		the set of points contained in the Steiner Hull from
		$c$ to $b$ with the edge $bc$, and $R_{2}$ is the set
		of points contained in the Steiner Polygon from $a$ to
		$d$ with the edge $ad$.  This decomposition is
		illustrated in
		Figure~\ref{fig:steiner_hull_extension}.  These three
		decomposition theorems will be combined in the parallel
		algorithm for decomposition presented next.

		\begin{figure}
		\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}

\textheight=9in
%\vspace*{11pt}
\newpage
\section{A Parallel Algorithm to Calculate the Steiner Hull}

	\vspace*{11pt}
	\subsection{A Introduction to Parallelism}

	Parallel computation is allowing us to look at problems that
	have previously been impossible to calculate, as well as
	allowing us to calculate faster than ever before problems we
	have looked at for a long time.  It is with this in mind that
	we begin to look at a parallel algorithm for the decomposition
	of the Steiner Minimal Tree problem.

	There have been volumes written on parallel computation and
	parallel algorithms; therefore, the author will not rehash the
	material that has already been so excellently covered by many
	others more knowledgeable on the topic, but will refer the
	interested readers to various books currently available.  For a
	thorough description of parallel algorithms, and the PRAM Model
	the reader is referred to the book by Joseph
	J\'aJ\'a~\cite{jaja:book}, and for a more practical approach to
	implementation on a parallel machine  the reader is referred to
	the book by Vipin Kumar et.al.~\cite{kggk:book} or the book by
	Justin Smith~\cite{smith:book}.

	\vspace*{11pt}
	\subsection{The Parallel Algorithm}

	The algorithm presented here is designed to operate on a CREW
	PRAM machine, which is a shared memory machine which allows
	concurrent reads from memory but allows only one processor to
	write to a specific location at a time.  Other models allow
	concurrent writing to the same location, but this requires an
	arbitration scheme for what is being written.

	This algorithm starts with its input being the Convex Hull for
	${\cal S}$. The vertices on the Convex Hull are placed in an
	array called {\it Edges}. This array is made up of structures,
	where each structure contains an integer (the vertex number)
	and two pointers that form a doubly linked list through the
	ordered entries.  Initially the linked list goes straight
	through the edges of the Convex Hull.  Two counters are kept
	for each round. The first counter is named {\it
	Previous\_count} and is initialized to $0$.  This counter keeps
	track of the count of the beginning vertex of the first edge
	alive on this round.  The second counter is named {\it
	Current\_count} and it is initialized to the number of edges in
	the Convex Hull.  This counter keeps track of where new edges
	created this round will begin to be placed.  Processor $i$ is
	assigned to the edge defined by vertices $i,i+1$ and the
	calculation begins.  Each processor determines whether the edge
	it was assigned is to be replaced via the Steiner Hull
	definition and it's extension.  An integer representing the
	number of edges that will replace this edge (0 -- no
	replacement, 2 -- standard Steiner Hull definition, or 3 --
	Steiner Hull Extension) is placed into {\it New\_Edges}[i].
	The prefix sum is then calculated for this array, which results
	in {\it New\_Edges}[i] = $\sum_{j=0}^{i}$.  This value
	determines the offset into {\it Edges} where the new edges are
	to be placed.  Processor $i$ places its new edges into the
	array beginning at {\it Current\_count} + {\it
	New\_Edges}[$i-1$].  Processor $i$ then updates the doubly
	linked list through {\it Edges}, starting with the previous
	link pointing to edge $i$, updating the list through the new
	edges, and then updating the next link at $i$.  The processor
	assigned to edge {\it Current\_count} - 1 then does the end of
	round updating:  $Previous\_count = Current\_count$,
	$Current\_count = Current\_count + New\_Edges[i]$.  For the
	next round the processors are assigned the edges from {\it
	Previous\_count} to {\it Current\_count}, and the calculation
	begins again.  This continues until $Previous\_count ==
	Current\_count$.

	When analyzing this algorithm, whose code is given in
	Figure~\ref{fig:parallel_steiner_hull_alg}, There is
	a case where only one edge will find a new set of edges to
	add to the current Steiner Polygon.  This makes the algorithm
	end up with ${\cal O}(n)$ rounds of computation.  In practice
	however, for the 100 point point problems we solved here, we
	never saw the algorithm go past 4 rounds of computation.

	\begin{figure}
		\vspace*{22pt}
	{\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} A parallel Steiner Hull algorithm.}
		\vspace*{22pt}
	\end{figure}

