\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}
An Introduction to \\
Steiner Minimal Trees on Grids\\
\quad \\
\quad \\
Frederick C. Harris, Jr.\\
fredh@cs.unr.edu\\
\quad \\
Department of Computer Science\\
University of Nevada\\
Reno, Nevada 89557
\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 P that minimizes\\
		 $dist(A, P)+dist(B,P) + dist(C,P)$ 
		\vspace{0.25in}
		\item Solved independently by Fermat, \\
		Torrichelli, and Cavalieri.
		\end{itemize}	

		\begin{figure}[h]
		\vspace*{22pt}
		\centerline{\psfig{figure=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}

	\newpage
		\item Computation Results

		\vspace{0.5in}
	        {\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}
	        }

 
	\end{itemize}

\newpage
\noindent
II. Grids

	\begin{itemize}
	\item 2 x m -- Chung and Graham ('78)
		\begin{itemize}
		\item If m is odd -- Full Steiner Tree

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

		\item If m is even -- $(\frac{m}{2}){\cal XI}$'s and ${\cal X}$

	        \begin{figure}[h]
		\centerline{\psfig{figure=grid.2.4.ps,height=2.0in}}
			\caption{\label{fig:grid.2.4}SMT for a 2 x 4 Grid}
		\end{figure}

		\end{itemize}

\newpage
	\item Building Blocks --\\ Chung, Gardner, Graham ('89)
        \begin{figure}[h]
        \centerline{\psfig{figure=grid.2.1.ps,height=1.9in}}
                \caption{\label{fig:BB-I}Building Block ${\cal I}$ }
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=grid.Y.ps,height=1.9in}}
                \caption{\label{fig:BB-Y}Building Block ${\cal Y}$}
	%	= $\frac{1+\sqrt{3}}{\sqrt{2}} \approx 1.93815$
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=grid.2.2.ps,height=1.9in}}
                \caption{\label{fig:BB-X}Building Block ${\cal X}$}  
	%	$1+ \sqrt{3} \approx 2.73205$
        \end{figure}

\newpage
	\item 3 x m

	        \begin{figure}[h]
	        \vspace*{22pt}
	        \centerline{\psfig{figure=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=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=grid.4.A.ps,width=3.75in}}
                \caption{\label{fig:grid.4.A}4 x m Pattern A}
		\end{figure}

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

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

\newpage

		\begin{figure}[h]
		\centerline{\psfig{figure=grid.4.E.ps,width=3.75in}}
                \caption{\label{fig:grid.4.E}4 x m Pattern E}
		\end{figure}

		\item Grammar Characterization

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

		\vspace{0.2in}
			\begin{enumerate}
			\item ${\cal B} \rightarrow {\cal C}$
			\item ${\cal C} \rightarrow {\cal BDB}$
			\item ${\cal DC} \rightarrow {\cal EAB}$
			\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|}\hline
		m = & 5 & 6 & 7 & 8  \\ \hline
		String & 
			${\cal AC}$ & 
			${\cal ABDB}$ & 
			${\cal ABDC}$ & 
			${\cal ABEAB}$ \\ \hline
	        \end{tabular}

		\vspace{0.25in}

		\begin{tabular}{|r|c|c|c|}\hline
		m = & 9 & 10 & 11 \\ \hline
		String & 
			${\cal ABEAC}$ & 
			${\cal ABEABDB}$ & 
			${\cal ABEABDC}$ \\ \hline
	        \end{tabular}
	        \end{center}
	        \end{table}
		}
		\end{itemize}

\newpage
	\item 5 x m
		\begin{itemize}

		\item Building Blocks

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.5.A.ps,height=1.9in}}
                \caption{\label{fig:grid.5.A}5 x m Pattern ${\cal A}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.5.B.ps,height=1.9in}}
                \caption{\label{fig:grid.5.B}5 x m Pattern ${\cal B}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.5.C.ps,height=1.9in}}
                \caption{\label{fig:grid.5.C}5 x m Pattern ${\cal C}$}
		\end{figure}

\newpage
       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.5.D.ps,height=1.9in}}
                \caption{\label{fig:grid.5.D}5 x m Pattern ${\cal D}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.5.E.ps,height=1.9in}}
                \caption{\label{fig:grid.5.E}5 x m Pattern ${\cal E}$}
		\end{figure}

\newpage
		\item Grammar Characterization

		Base: ${\cal EA'B}$

		5 x 5 grid is:  Base ${\cal D}$

		\begin{enumerate}
			\item ${\cal C} \rightarrow {\cal B'D'}$
			\item ${\cal D} \rightarrow {\cal A'E}$
			\item ${\cal E} \rightarrow {\cal AC}$
			\item ${\cal C'} \rightarrow {\cal BD}$
			\item ${\cal D'} \rightarrow {\cal AE'}$
			\item ${\cal E'} \rightarrow {\cal A'C'}$
		\end{enumerate}

		{\Large
	        \begin{table}[h]
	        \caption{\label{table:grid.5.m} 
			String Representations for 5 x m Grids}

		\begin{center}
		\begin{tabular}{|r|c|c|c|c|}\hline
		m = & 5 & 6 & 7 & 8  \\ \hline
		String & ${\cal EA'BD}$ & ${\cal EA'BA'E}$ & 
			${\cal EA'BA'AC}$ & ${\cal EA'BA'AB'D'}$  \\ \hline
	        \end{tabular}

		\vspace{0.25in}

		\begin{tabular}{|r|c|c|c|}\hline
		m = & 9 & 10 & 11 \\ \hline
		String & ${\cal EA'BA'AB'AE'}$ & 
			${\cal EA'BA'AB'AA'C'}$ & 
			${\cal EA'BA'AB'AA'BD}$ \\ \hline
	        \end{tabular}
	        \end{center}
	        \end{table}
		}

		\end{itemize}
\newpage
	\item 6 x m
		\begin{itemize}
		\item Building Blocks

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.6.A.ps,height=1.9in}}
                \caption{\label{fig:grid.6.A}6 x m Pattern ${\cal A}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.6.B.ps,height=1.9in}}
                \caption{\label{fig:grid.6.B}6 x m Pattern ${\cal B}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.6.C.ps,height=1.9in}}
                \caption{\label{fig:grid.6.C}6 x m Pattern ${\cal C}$}
		\end{figure}

\newpage
       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.6.D.ps,height=1.9in}}
                \caption{\label{fig:grid.6.D}6 x m Pattern ${\cal D}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.6.E.ps,height=1.9in}}
                \caption{\label{fig:grid.6.E}6 x m Pattern ${\cal E}$}
		\end{figure}

\newpage
		\item Grammar Characterization

		6 x 3 grid is ${\cal AC}$

		\begin{enumerate}
			\item ${\cal C} \rightarrow {\cal BD}$
			\item ${\cal D} \rightarrow {\cal EC}$
		\end{enumerate}
	
		\item Regular Expression :

			${\cal A(BE)^{*}(C|BD)}$
		\end{itemize}

		{\Large
	        \begin{table}[h]
	        \caption{\label{table:grid.6.m} 
			String Representations for 6 x m Grids}

		\begin{center}
		\begin{tabular}{|r|c|c|c|}\hline
		m = & 6 & 7 & 8  \\ \hline
		String & 
			${\cal ABEBD}$ & 
			${\cal ABEBEC}$ & 
			${\cal ABEBEBD}$  \\ \hline
	        \end{tabular}

		\vspace{0.25in}

		\begin{tabular}{|r|c|c|c|}\hline
		m = & 9 & 10 & 11 \\ \hline
		String & 
			${\cal ABEBEBEC}$ & 
			${\cal ABEBEBEBD}$ & 
			${\cal ABEBEBEBEC}$ \\ \hline
	        \end{tabular}
	        \end{center}
	        \end{table}
		}
\newpage
	\item 7 x m
		\begin{itemize}
		\item Building Blocks

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.A.ps,height=1.9in}}
                \caption{\label{fig:grid.7.A}7 x m Pattern ${\cal A}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.B.ps,height=1.9in}}
                \caption{\label{fig:grid.7.B}7 x m Pattern ${\cal B}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.C.ps,height=1.9in}}
                \caption{\label{fig:grid.7.C}7 x m Pattern ${\cal C}$}
		\end{figure}
\newpage
       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.D.ps,height=1.9in}}
                \caption{\label{fig:grid.7.D}7 x m Pattern ${\cal D}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.E.ps,height=1.9in}}
                \caption{\label{fig:grid.7.E}7 x m Pattern ${\cal E}$}
		\end{figure}

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.F.ps,height=1.9in}}
                \caption{\label{fig:grid.7.F}7 x m Pattern ${\cal F}$}
		\end{figure}

\newpage
		\item Grammar Characterization

		Base: ${\cal FA'}$

		7 x 5 grid is:  Base ${\cal E'F'}$

		\begin{enumerate}
			\item ${\cal E'F'} \rightarrow {\cal BA'F}$
			\item ${\cal F} \rightarrow {\cal CD}$
			\item ${\cal CD} \rightarrow {\cal AEF}$
			\item ${\cal EF} \rightarrow {\cal B'AF'}$
			\item ${\cal F'} \rightarrow {\cal C'D'}$
			\item ${\cal C'D'} \rightarrow {\cal A'E'F'}$
		\end{enumerate}

		{\Large
	        \begin{table}[h]
	        \caption{\label{table:grid.7.m} 
			String Representations for 7 x m Grids}

		\begin{center}
		\begin{tabular}{|r|c|c|c|}\hline
		m = & 7 & 8 & 9  \\ \hline
		String & 
			${\cal FA'BA'CD}$ & 
			${\cal FA'BA'AEF}$ & 
			${\cal FA'BA'AB'AF'}$  \\ \hline
	        \end{tabular}

		\vspace{0.25in}

		\begin{tabular}{|r|c|c|c|}\hline
		m = & 10 & 11 & 12 \\ \hline
		String & 
			${\cal FA'BA'AB'AC'D'}$ & 
			${\cal FA'BA'AB'AA'E'F'}$ & 
			${\cal FA'BA'AB'AA'BA'F}$ \\ \hline
	        \end{tabular}
	        \end{center}
	        \end{table}
		}
		\end{itemize}
\newpage
	\item 8 x m
       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.8.8.ps,height=2in}}
                \caption{\label{fig:grid.8.8}8 x 8 }
		\end{figure}

		\begin{itemize}
		\item Work was going great until here.
		\item I haven't cleaned up the grammar, so I will just
			give the pattern.
		\end{itemize}

		\begin{itemize}
		\item 8 x 8 = given above in Figure~\ref{fig:grid.8.8}
		\item 8 x 9 = Three 8 x 3's linked
		\item 8 x 10 =  8 x 8 + 8 x 2
		\item 8 x 11 = 8 x 8 + 8 x 3
		\item 8 x 12 = 8 x 8 + 8 x 4
		\item 8 x 13 = 8 x 8 + 8 x 5
		\item 8 x 14 = 8 x 8 + 8 x 6
		\item 8 x 15 = 8 x 8 + 8 x 7
		\item 8 x 16 = 8 x 8 + 8 x 8
		\item 8 x 17 = 8 x 8 + 8 x 9
		\end{itemize}
	\end{itemize}

%\newpage
%\noindent
%III. Future Work
%	\begin{itemize}
%	\item m x n grids
%	\end{itemize}
\end{document}
