\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}
Steiner Minimal Trees on Grids\\
\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 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}


	\newpage
	\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}

	\vspace{1in}

	\item First Algorithm
		\begin{itemize}
		\item Melzak ('61)
		\vspace{0.45in}
		\item Replace two points with a third.
		\vspace{0.45in}
		\item $T(n)=2*\left( \begin{array}{c}n\\2\end{array}
			\right)*T(n-1).$
		\vspace{0.35in}
		\end{itemize}
	\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}$}
        \end{figure}

        \begin{figure}[h]
        \centerline{\psfig{figure=grid.2.2.ps,height=1.9in}}
                \caption{\label{fig:BB-X}Building Block ${\cal X}$}
        \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
	\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
%III. Future Work
%	\begin{itemize}
%	\item m x n grids
%	\end{itemize}
\end{document}
