
\documentstyle[12pt]{article}
\textwidth=6.0in
\textheight=9.25in
\evensidemargin=0.25in
\oddsidemargin=0.25in
\topmargin=-0.75in
%\topskip=0pt
\baselineskip=12pt
\parskip=0pt
\parindent=0em
\input psfig
\begin{document}
\title{An Introduction \\ to Steiner Minimal Trees on Grids}
\author{ Frederick C. Harris, Jr.\\
fredh@cs.unr.edu\\
\\
Department of Computer Science\\
University of Nevada\\
Reno, Nevada 89557
}
\date{\quad}
\maketitle

\addcontentsline{toc}{section}{Abstract}
%\parskip=4pt
\begin{abstract}
        The optimization problem is simply stated as follows:  Given a
        set of  $N$ cities, construct a connected network which has
        minimum length.  The problem is simple enough, but the catch is
        that you are allowed to add junctions in your network.
        Therefore the problem becomes how many extra junctions should
        be added, and where should they be placed, so as to minimize the
        overall network length.

	This intriguing optimization problem is also known as the
	Steiner Minimal Tree Problem, where the junctions that are
	added to the network are called Steiner Points.  What is known
	about the general problem will be presented first and then the
	focus will turn from the general problem to the problem on a
	lattice of points called a grid.

	The characterization of the Steiner Minimal Tree (SMT) for a $2
	\times  m$ grid is generally known, %to be the Full Steiner Tree
	%on the vertices of the grid, 
	while the only other conjectured
	characterizations for grids previously known were for square
	grids.  We will present the characterization of SMT's for $2
	\times m$ grids, as well as characterizations of
	SMT's for grids up through $7 \times  m$.

{\bf Keywords:} Steiner Minimal Trees, Grids
\end{abstract}

\bibliographystyle{plain}
\parindent=1em

\section{The Problem}

        \hspace{1em}Minimizing a network's length is one of the oldest
        optimization problems in mathematics and, consequently, it has
        been worked on by many of the leading mathematicians in
        history.  In the mid-seventeenth century a simple problem was
        posed:  Find the point $P$ that minimizes the sum of the
        distances from $P$ to each of three given points in the plane.
        Solutions to this problem were derived independently by Fermat,
        Torricelli and Cavalieri.  They all deduced that either $P$ is
        inside the triangle formed by the given points and that the
        angles at $P$ formed by the lines joining $P$ to the three
        points are all $120^{\circ}$, or $P$ is one of the three
        vertices and the angle at $P$ formed by the lines joining $P$
        to the other two points is greater than or equal to
        $120^{\circ}$.

        In the nineteenth century a mathematician at the University of
        Berlin named Jakob Steiner studied this problem and
        generalized it to include an arbitrarily large set of points in
        the plane.  This generalization created a star when $P$ was
        connected to all the given points in the plane and is a
        geometric approach to the 2-dimensional center of mass
        problem.

        In 1934 K\"{o}ssler and Jarn\'{i}k generalized the network
        minimization problem even further~\cite{jk34:omgodb}:  Given
        $n$ points in the plane find the shortest possible connected
        network containing these points.  This generalized problem,
        however, did not become popular until the book {\it What is
        Mathematics} by Courant and Robbins~\cite{cr41:wim} was
	published
        in 1941. Courant and Robbins linked the name Steiner with this
        form of the problem proposed by K\"{o}ssler and Jarn\'{i}k, and
        it became known as the Steiner Minimal Tree (SMT) problem.  The
        general solution to this problem allows multiple points to be
        added, each of which is called a Steiner Point, creating a tree
        instead of a star.

        Much is known about the exact solution to the Steiner Minimal
        Tree problem.  Those who wish to learn about some of the
        spin-off problems are invited to read the introductory article
        by Bern and Graham~\cite{bg89:tsnp}, the excellent survey paper
        on this problem by Hwang and Richards~\cite{hr92:survey}, or
        the recent volume in The Annals of Discrete Mathematics devoted
        completely to Steiner Tree problems~\cite{hrw:annals}.  Some of
        the basic pieces of information about the Steiner Minimal Tree
        problem that can be gleaned from these articles are: (i) 
        all of the original $n$ points will be of degree 1,
        2, or 3, (ii) the Steiner Points are all of degree 3, (iii) any
        two edges meet at an angle of at least $120^{\circ}$ in the
        Steiner Minimal Tree, and (iv) at most $n-2$ Steiner Points
        will be added to the network.

	In Section~\ref{sec:first_solution} we review the first
	fundamental algorithm generally known for calculating SMT's.  
	In Section~\ref{sec:current_results} we look at the current
	computational results for finding SMT's.  In 
	Section~\ref{sec:grids} we present what is currently known 
	about SMT's on grids and then introduce SMT's for other 
	grid networks.  Finally we present some ambitious future 
	work in Section~\ref{sec:future_work}.

\section{The First Solution}
	\label{sec:first_solution}

        \hspace{1em} A typical problem-solving approach is to begin
        with the simple cases and expand to a general solution.  As we
        saw in Section 1, the trivial three point problem had already
        been solved in the 1600's, so all that remained was the work
        toward a general solution.  As with many interesting problems
        this is harder than it appears on the surface.

        The method proposed by the mathematicians of the
        mid-seventeenth century for the three point problem is
        illustrated in Figure~\ref{fig:melzak}.  This method stated
        that in order to calculate the Steiner Point given points A, B,
        and C, you first construct an equilateral triangle $(ACX)$
        using the longest edge between two of the points $(AC)$ such
        that the third $(B)$ lies outside the triangle.  A circle is
        circumscribed around the triangle, and a line is constructed
        from the third point $(B)$ to the far vertex of the triangle
        $(X)$.  The location of the Steiner Point $(P)$ is the
        intersection of this line $(BX)$ with the circle.

        \begin{figure}
        \centerline{\psfig{figure=fig-melzak.ps,height=2.1in}}
                \caption{\label{fig:melzak}AP + CP = PX.}
        \end{figure}

        For the next thirty years after  K\"{o}ssler and Jarn\'{i}k
        presented the general form of the SMT problem, the only
        algorithms that existed were heuristics.  The heuristics were
        typically based upon the Minimum-Length Spanning Tree (MST),
        which is a tree that spans or connects all vertices whose sum
        of the edge lengths is as small as possible, and tried in
        various ways to join three vertices with a Steiner Point.  In
        1968 Gilbert and Pollak~\cite{gp68:smt} linked the length of
        the SMT to the length of a MST.  It was already known that the
        length of an MST is an upper bound for the length of an SMT,
        but their conjecture stated that the length of an SMT would
        never be any shorter than $\frac{\sqrt{3}}{2}$ times the length
        of an MST.  This conjecture was recently
        proved~\cite{dh92:apotgpcotsr} and has led to the MST being
        the starting point for most of the heuristics that have been
        proposed in the last 20 years \cite{harris:asoafsmt,hrw:annals}.

        In 1961 Melzak developed the first known algorithm for 
	calculating an SMT~\cite{melzak61:otpos}.  Melzak's 
	Algorithm was geometric in nature and was based upon some 
	simple extensions to Figure~\ref{fig:melzak}.  The insight 
	that Melzak offered was
        the fact that you can reduce an $n$ point problem to a set of
        $n-1$ point problems.  This reduction in size is accomplished
        by taking every pair of points, A and C in our example,
        calculating where the two possible points, $X_{1}$ and
        $X_{2}$,  would be that form equilateral triangles with them,
        and creating two smaller problems, one where $X_{1}$ replaces A
        and C, and the other where $X_{2}$ replaces A and C.  
	Melzak's  algorithm can then be run
        on the two smaller problems.  This recursion, based upon
        replacing two points with one point,  finally terminates when
        you reduce the problem from three to two vertices.  At this
        termination the length of the tree will be the length of the
        line segment connecting the final two points.  This is due to
        the fact that $BP + AP + CP = BP + PX$.  This is
        straightforward to prove using the law of cosines, for when $P$
        is on the circle, $\angle APX = \angle CPX = 60^{\circ} $.
        This allows the calculation of the last Steiner Point (P) and
        allows you to back up the recursive call stack to calculate
        where each Steiner Point in that particular tree is located.
\newpage

        This reduction is important in the calculation of an SMT, but
        the algorithm still has exponential order, since it requires
        looking at every possible reduction of a pair of points to a
        single point.  The recurrence relation for an $n$-point problem
        is stated quite simply in the following formula:
        \[
        T(n)=2*\left( \begin{array}{c}n\\2\end{array}\right)*T(n-1).
        \]
        This yields what is obviously a non-polynomial time algorithm.
        In fact Garey, Graham, and Johnson~\cite{ggj77:tcocsmt} have
        shown that the Steiner Minimal Tree problem is NP-Hard
        (NP-Complete if the distances are rounded up to discrete
        values).

\section{Current Results}
	\label{sec:current_results}

	\hspace{1em}In 1967, just a few years after Melzak's paper,
	Cockayne~\cite{cockayne67:otsp} clarified some of the details
	from Melzak's proof and proposed a new term, the ``steiner
	hull''~\cite{cockayne70:oteotafsmt}.  The steiner hull was the
	foundation for the first decomposition algorithm for the SMT
	problem.  This decomposition, along with a clarified algorithm,
	proved to be the basis for the first computer program to
	calculate SMTs, which appeared in~\cite{cs72:cosmt}, and which
	could compute an SMT for any placement of up to $7$ vertices.

	The biggest breakthrough after Cockayne's algorithm came from
	Winter in 1985~\cite{winter85:aaftspitep}  who was able to
	establish some geometric results that enabled one to eliminate
	(prune out) a great many of the reconstruction sequences
	required by Melzak's algorithm.  Using this, Winter was able to
	compute SMTs for 15 or fewer vertices.  Winter's algorithm has
	been the basis for most of the enhancements in SMT algorithms
	since then.

	In 1986 another major computational breakthrough was made.
	Cockayne and Hewgill~\cite{ch86:ecosmtitp}  were able to
	calculate the SMT for up to 30 vertices 80\% of the time.  They
	achieved this through the use of what they termed an
	incompatibility matrix, which took the sub-trees left after
	Winter's pruning and determined whether trees $i$ and $j$ could
	appear together in the SMT.

	Most of the rest of the current results for exact computation
	of SMTs belong to Cockayne and Hewgill.  In 1992 they developed
	better pruning techniques that have allowed them to calculate
	SMTs for up to 100 vertices 80\% of the time.  Their paper
	describing these results~\cite{ch92:icopsmt} recently appeared
	in a special issue of {\it Algorithmica} devoted exclusively to
	the Steiner Problem.

	The last major breakthrough belongs to the author.  His work
	involved complete parallelization of the construction of
	SMTs.  While it is still under modification, this method has
	reduced the computation time by at least an order of magnitude
	and methods under examination may lead to further improvements
	\cite{harris:dissertation,harris:pcosmt}.
	Table~\ref{tab:computation_results} provides a summary of the
	major programs written to solve the SMT problem and their
	capabilities.

	\begin{table}
	\begin{center}
	\begin{tabular}{|l|l|l|r|}\hline
	Program	& Author(s) 		&  Location 	& Points \\ \hline
        STEINER~\cite{cs72:cosmt}
		& Cockayne \& Schiller & Univ of Victoria 	& 7  \\ \hline
        STEINER72~\cite{bs75:aivocspsftmnp} 
		& Boyce \& Serry  	&  ATT Bell Labs 	& 10 \\ \hline
        STEINER73~\cite{cockayne:private_comm}
		& Boyce \& Serry 	& ATT Bell Labs 	& 12 \\ \hline
        GEOSTEINER~\cite{winter85:aaftspitep} 
		& Winter 		& Univ of Copenhagen 	& 15 \\ \hline
        EDSTEINER86~\cite{ch86:ecosmtitp}
		& Cockayne \& Hewgill 	& Univ of Victoria 	& 30 \\ \hline
        EDSTEINER89~\cite{ch92:icopsmt}
		& Cockayne \& Hewgill 	& Univ of Victoria 	& 100\\ \hline
        PARSTEINER94~\cite{harris:dissertation,harris:pcosmt}
		& Harris 		& Clemson University 	& 100\\ \hline
	\end{tabular}
        \caption{\label{tab:computation_results}Computation Results}
	\end{center}
	\end{table}

 

\section{Grids}
	\label{sec:grids}

	\hspace{1em}The problem of determining SMTs for grids was
	mentioned to the author by Ron Graham.  In this context we are
	thinking of a grid as a regular lattice of unit squares.  The
	literature has little of information regarding SMTs on grids,
	and most of the information that is given is conjectured and
	not proven.  In Section~\ref{sec:2_by_m} we will look at what
	is known about SMTs on grids.  In the following sub-sections
	we will introduce new results for grids up through $7 \times m$
	in size.  The new results presented are computational results
	from PARSTEINER94~\cite{harris:dissertation,harris:pcosmt}
	which was discussed in the previous section.

	\subsection{\label{sec:2_by_m}$2 \times m$ and Square Grids}

	\hspace{1em}The first proof for anything besides a $2 \times 2$
	grid came in a paper by Chung and Graham~\cite{cg:stfl} in
	which they proved the optimality of their characterization of
	SMTs for $2 \times m$ grids.  The only other major work was
	presented in a paper by Chung, Gardner, and
	Graham~\cite{cgg:stoac}.  They argued the optimality of the SMT
	on $2 \times 2$, $3 \times 3$, and $4 \times 4$ grids and gave
	conjectures and constructions for those conjectures for SMTs
	on all other square lattices.

	In their work Chung, Gardner, and Graham specified three
	building blocks from which all SMTs on square ($n \times n$)
	lattices were constructed.  The first, labeled ${\cal I}$, is
	just a $K_{2}$, or a path on two vertices.  This building block
	is given in Figure~\ref{fig:BB}-A.  The second, labeled ${\cal
	Y}$, is a Full Steiner Tree (FST) ($n$ vertices and $n-2$
	steiner points) on 3 vertices of the unit square.  This
	building block is given in Figure~\ref{fig:BB}-B.  The third,
	labeled ${\cal X}$, is an FST on all 4 vertices of the unit
	square.  This building block is given in
	Figure~\ref{fig:BB}-C.  For the generalizations we are going to
	make here, we need to introduce one more building block, which
	we will label ${\cal S}$.  This building block is an FST on a $3
	\times  2$ grid and appears in Figure~\ref{fig:BB}-D.

	\begin{figure}
	\centerline{\psfig{figure=blocks.ps,height=1.0in}}
	\caption{\label{fig:BB}Building Blocks}
	%\caption{\label{fig:BB-I}Building Block ${\cal I}$ }
	%\caption{\label{fig:BB-Y}Building Block ${\cal Y}$}
	%	= $\frac{1+\sqrt{3}}{\sqrt{2}} \approx 1.93815$
        %\caption{\label{fig:BB-X}Building Block ${\cal X}$}  
	%	$1+ \sqrt{3} \approx 2.73205$
        \end{figure}

	SMTs for grids of size $2 \times m$ have two basic structures.
	The first is an FST on all the vertices in the $2 \times  m$
	grid.  An example of this for a $2 \times 3$ grid is given in
	Figure~\ref{fig:BB}-D.  The other structure is constructed from
	the building blocks previously described. We hope that these
	building blocks, when put in conjunction with the
	generalizations for $3 \times  m$, $4 \times m$,  $5 \times m$,
	$6 \times m$, and $7 \times m$ will
	provide the foundation for a generalization of $m \times n$
	grids in the future.

	In their work on ladders ($2 \times m$ grids) Chung and Graham
	established and proved the optimality of their characterization
	for $2 \times m$ grids.  Before giving their characterization,
	a brief review of the first few $2 \times m$ SMTs is in order.
	The SMT for a $2 \times 2$ grid is shown in
	Figure~\ref{fig:BB}-C, the SMT for a $2 \times 3$ grid is shown
	in Figure~\ref{fig:BB}-D, and the SMT for a $2 \times 4$ grid
	is given in Figure~\ref{fig:grid.2.4}.

	Chung and Graham~\cite{cg:stfl} proved that SMTs for ladders
	fell into one of two categories.  If the length of the ladder
	was odd, then the SMT was the FST on the vertices of the
	ladder.  The SMT for the $2 \times 3$ grid in
	Figure~\ref{fig:BB}-D is an example of this. If the length of
	the ladder was even, the SMT was made up of a series of
	$(\frac{m}{2}-1)$ ${\cal XI}$'s followed by one last ${\cal
	X}$.  The SMT for the $2 \times 4$ grid in
	Figure~\ref{fig:grid.2.4} is an example of this.


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


	\subsection{$3 \times m$ Grids}

	\hspace{1em} The SMT for $3 \times m$ grids has a very easy
	characterization which can be seen once the initial cases have
	been presented.  The SMT for the $3 \times 2$ grid is presented
	in Figure~\ref{fig:BB}-D.  The SMT for the $3 \times 3$ grid is
	presented in Figure~\ref{fig:grid.3.3}.

	        \begin{figure}
	        \centerline{\psfig{figure=grid.3.3.ps,height=1.0in}}
                \caption{\label{fig:grid.3.3}SMT for a $3 \times 3$ Grid}
	        \end{figure}
	
	From here we can characterize all $3 \times m$ grids.  Except
	for in the $3 \times 2$ grid, which is an ${\cal S}$ building block,
	there will be only two basic building blocks present, ${\cal
	X}$'s and ${\cal I}$'s.  There will be exactly two ${\cal I}$'s
	and $(m-1)$${\cal X}$'s.  The two ${\cal I}$'s  will appear on
	each end of the grid.  The ${\cal X}$'s will appear in a
	staggered checkerboard pattern, one on each column of the grid
	the same way that the two ${\cal X}$'s are staggered in the $3
	\times 3$ grid.  The $3 \times 5$ grid is a good example of
	this and is shown in Figure~\ref{fig:grid.3.5}.


	        \begin{figure}[h]
	        \centerline{\psfig{figure=grid.3.5.ps,height=1.0in}}
                \caption{\label{fig:grid.3.5}SMT for a $3 \times 5$ Grid}
	        \end{figure}

	\subsection{$4 \times m$ Grids}

	\hspace{1em}The foundation for the $4 \times m$ grids has
	already been laid.  In their most recent work, Cockayne and
	Hewgill presented some results on Square Lattice
	Problems~\cite{ch92:icopsmt}.  They looked at $4 \times m$
	grids for $m=2$ to $m=6$.  They also looked at the SMTs for
	these problems when various lattice points in that grid were
	missing.  What they did not do, however, was characterize the
	structure of the SMT's for all $4 \times m$ grids.

	The $4 \times 2$ grid is given in Figure~\ref{fig:grid.2.4}.
	From the work of  Chung, Gardner, and Graham~\cite{cgg:stoac},
	we know that the SMT for a $4 \times 4$ grid is a checkerboard
	pattern of 5 ${\cal X}$'s.  This layout gives us the first two
	patterns we will need to describe the $4 \times m$
	generalization.  The first pattern, which we will call pattern
	${\cal A}$,  is the same as the $3 \times 4$ grid without the
	two ${\cal I}$'s on the ends.  This pattern is given in
	Figure~\ref{fig:grid.4.A}.  The second pattern, denoted as
	pattern ${\cal B}$,  is the $2 \times 4$ grid in
	Figure~\ref{fig:grid.2.4} without the connecting ${\cal I}$.
	This is shown in Figure~\ref{fig:grid.4.B}.

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.4.A.ps,width=1.0in}}
                \caption{\label{fig:grid.4.A}$4 \times m$ Pattern ${\cal A}$}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.4.B.ps,width=1.0in}}
                \caption{\label{fig:grid.4.B}$4 \times m$ Pattern ${\cal B}$}
		\end{figure}

	Before the final characterization can be made, two more
	patterns are needed.  The first one, called pattern ${\cal C}$,
	is a $4 \times 3$ grid where the pattern is made up of two
	non-connected $2 \times 3$ SMTs, shown in
	Figure~\ref{fig:grid.4.C}.  The next pattern, denoted pattern
	${\cal D}$, is quite simply a ${\cal Y}$ centered in a $2
	\times 4$ grid.  This is shown in Figure~\ref{fig:grid.4.D}.
	The final pattern, denoted ${\cal E}$, is just an ${\cal I}$ on
	the right side of a $2 \times 4$ grid.  This is shown in
	Figure~\ref{fig:grid.4.E}.

	Now we can begin the characterization.  The easiest way to
	present the characterization is with some simple string
	rewriting rules.  Since the $4 \times 2$, $4 \times 3$, and $4
	\times 4$ patterns have already been given, the rules will
	begin with a $4 \times 5$ grid.  This grid has the string
	${\cal AC}$.  The first rule is that whenever there is a ${\cal
	C}$ on the right end of your string replace it with ${\cal
	BDB}$.  Therefore a $4 \times 6$ grid is ${cal ABDB}$.  The
	next rule is that whenever there is a ${\cal B}$ on the right
	end of your string replace it with a ${\cal C}$.  The final
	rule is whenever there is a ${\cal DC}$ on the right end of
	your string replace it with an ${\cal EAB}$.  These rules are
	summarized in Table~\ref{tab:4_by_rules}.  A listing of the
	strings for $m$ from 5 to 11 is given in
	Table~\ref{table:grid.4.m}.

	\begin{figure}[h]
	\centerline{\psfig{figure=grid.4.C.ps,width=1.0in}}
               \caption{\label{fig:grid.4.C}$4 \times m$ Pattern ${\cal C}$}
		\vspace{0.2in}
	\centerline{\psfig{figure=grid.4.D.ps,width=1.0in}}
               \caption{\label{fig:grid.4.D}$4 \times m$ Pattern ${\cal D}$}
		\vspace{0.2in}
	\centerline{\psfig{figure=grid.4.E.ps,width=1.0in}}
               \caption{\label{fig:grid.4.E}$4 \times m$ Pattern ${\cal E}$}
	\end{figure}

	\begin{table}[h]
	\begin{center}
	\begin{tabular}{|l|l|} \hline
	1 & ${\cal B} \rightarrow {\cal C}$ \\ \hline
	2 & ${\cal C} \rightarrow {\cal BDB}$ \\ \hline
	3 & ${\cal DC} \rightarrow {\cal EAB}$ \\ \hline
	\end{tabular}
	\end{center}
	\caption{\label{tab:4_by_rules} Rewrite rules for $4 \times 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.2in}

		\begin{tabular}{|r|c|c|c|}\hline
		m = & 9 & 10 & 11 \\ \hline
		String & 
			${\cal ABEAC}$ & 
			${\cal ABEABDB}$ & 
			${\cal ABEABDC}$ \\ \hline
	        \end{tabular}
        \end{center}
        \caption{\label{table:grid.4.m} 
		String Representations for $4 \times m$ Grids}
        \end{table}

	\subsection{$5 \times m$ Grids}

		\hspace{1em}For the $5 \times m$ grids there are 5
		building blocks (and their mirror images which are
		donated with an ${\cal '}$) that are used to generate
		any $5 \times m$ grid.  These building blocks appear in
		Figure~\ref{fig:grid.5.A}, Figure~\ref{fig:grid.5.B},
		Figure~\ref{fig:grid.5.C}, Figure~\ref{fig:grid.5.D},
		and Figure~\ref{fig:grid.5.E}.

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.5.A.ps,height=1.0in}}
                \caption{\label{fig:grid.5.A}$5 \times m$ Pattern ${\cal A}$}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.5.B.ps,height=1.0in}}
                \caption{\label{fig:grid.5.B}$5 \times m$ Pattern ${\cal B}$}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.5.C.ps,height=1.0in}}
                \caption{\label{fig:grid.5.C}$5 \times m$ Pattern ${\cal C}$}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.5.D.ps,height=1.0in}}
                \caption{\label{fig:grid.5.D}$5 \times m$ Pattern ${\cal D}$}
		\end{figure}

		\begin{figure} [h]
		\centerline{\psfig{figure=grid.5.E.ps,height=1.0in}}
                \caption{\label{fig:grid.5.E}$5 \times m$ Pattern ${\cal E}$}
		\end{figure}
\newpage
		With the building blocks in place, the characterization
		of $5 \times m$ grids is quite easy using grammar
		rewrite rules.  The rules used for rewriting strings
		representing a $5 \times m$ grid are given in
		Table~\ref{tab:5_by_rules}.  The SMTs for $5 \times 2$,
		$5 \times 3$, and $5 \times 4$ have already been
		given.  For a $5 \times 5$ grid the SMT is made up of
		the following string: ${\cal EA'BD}$.  As a reminder,
		the ${\cal A'}$ signifies the mirror of building block
		${\cal A}$.  A listing of the strings for $m$ from 5 to
		11 is given in Table~\ref{table:grid.5.m}.

	        \begin{table}[h]
		\begin{center}
		\begin{tabular}{|l|l|} \hline
		1 & ${\cal C} \rightarrow {\cal B'D'}$ \\ \hline
		2 & ${\cal D} \rightarrow {\cal A'E}$ \\ \hline
		3 & ${\cal E} \rightarrow {\cal AC}$ \\ \hline
		4 & ${\cal C'} \rightarrow {\cal BD}$ \\ \hline
		5 & ${\cal D'} \rightarrow {\cal AE'}$ \\ \hline
		6 & ${\cal E'} \rightarrow {\cal A'C'}$ \\ \hline
		\end{tabular}
		\end{center}
		\caption{\label{tab:5_by_rules}
			Rewrite rules for $5 \times 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}
	        \caption{\label{table:grid.5.m} 
			String Representations for $5 \times m$ Grids}
	        \end{table}

	\subsection{$6 \times m$ Grids}
		\hspace{1em}For the $6 \times m$ grids there are 5
		building blocks that are used to generate any $6 \times
		m$ grid.  These building blocks appear in
		Figure~\ref{fig:grid.6.A}, Figure~\ref{fig:grid.6.B},
		Figure~\ref{fig:grid.6.C}, Figure~\ref{fig:grid.6.D},
		and Figure~\ref{fig:grid.6.E}.


       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.6.A.ps,height=1.0in}}
                \caption{\label{fig:grid.6.A}$6 \times m$ Pattern ${\cal A}$}
       		\end{figure}
       		\begin{figure}
		%\vspace{0.2in}
		\centerline{\psfig{figure=grid.6.B.ps,height=1.0in}}
                \caption{\label{fig:grid.6.B}$6 \times m$ Pattern ${\cal B}$}
       		\end{figure}

       		\begin{figure}
		%\vspace{0.2in}
		\centerline{\psfig{figure=grid.6.C.ps,height=1.0in}}
                \caption{\label{fig:grid.6.C}$6 \times m$ Pattern ${\cal C}$}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.6.D.ps,height=1.0in}}
                \caption{\label{fig:grid.6.D}$6 \times m$ Pattern ${\cal D}$}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.6.E.ps,height=1.0in}}
                \caption{\label{fig:grid.6.E}$6 \times m$ Pattern ${\cal E}$}
		\end{figure}

		The solution for $6 \times m$ grids can now be
		characterized by using grammar rewrite rules.  The
		rules used for rewriting strings representing a $6
		\times m$ grid are given in
		Table~\ref{tab:6_by_rules}.  The basis for this rewrite
		system is the SMT for the $6 \times 3$ grid which is
		${\cal AC}$.  It is also nice to see that for the $6
		\times m$ grids there is a simple regular expression
		which can characterize what the string will be.  That
		regular expression has the form: ${\cal
		A(BE)^{*}(C|BD)}$.  A listing of the strings for $m$
		from 6 to 11 is given in Table~\ref{table:grid.6.m}.

	        \begin{table}
		\begin{center}
		\begin{tabular}{|l|l|} \hline
		1 & ${\cal C} \rightarrow {\cal BD}$ \\ \hline
		2 & ${\cal D} \rightarrow {\cal EC}$ \\ \hline
		\end{tabular}
		\end{center}
		\caption{\label{tab:6_by_rules}
			Rewrite rules for $6 \times m$ Grids}
		\end{table}

		\begin{table}
		\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.2in}

		\begin{tabular}{|r|c|c|c|}\hline
		$m$ = & 9 & 10 & 11 \\ \hline
		String & 
			${\cal ABEBEBEC}$ & 
			${\cal ABEBEBEBD}$ & 
			${\cal ABEBEBEBEC}$ \\ \hline
	        \end{tabular}
	        \end{center}
	        \caption{\label{table:grid.6.m} 
			String Representations for $6 \times m$ Grids}
	        \end{table}

	\subsection{$7 \times m$ Grids}
		\hspace{1em}For the $7 \times m$ grids there are 6
		building blocks that are used to generate any $7 \times
		m$ grid.  These building blocks appear in
		Figure~\ref{fig:grid.7.A}, Figure~\ref{fig:grid.7.B},
		Figure~\ref{fig:grid.7.C}, Figure~\ref{fig:grid.7.D},
		Figure~\ref{fig:grid.7.E}, and
		Figure~\ref{fig:grid.7.F}.

		The grammar rewrite rules for strings representing a $7
		\times m$ grid are given in
		Table~\ref{tab:7_by_rules}.  The basis for this rewrite
		system is the SMT for the $7 \times 5$ grid which is
		${\cal FA'E'F'}$.  A listing of the strings for $m$
		from 6 to 11 is given in Table~\ref{table:grid.7.m}.

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.7.A.ps,height=1.0in}}
                \caption{\label{fig:grid.7.A}$7 \times m$ Pattern ${\cal A}$}
		%\end{figure}
		%\begin{figure}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.7.B.ps,height=1.0in}}
                \caption{\label{fig:grid.7.B}$7 \times m$ Pattern ${\cal B}$}
		%\end{figure}
		%\begin{figure}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.7.C.ps,height=1.0in}}
                \caption{\label{fig:grid.7.C}$7 \times m$ Pattern ${\cal C}$}
		%\end{figure}
		%\begin{figure}
		\vspace{0.2in}
		\centerline{\psfig{figure=grid.7.D.ps,height=1.0in}}
                \caption{\label{fig:grid.7.D}$7 \times m$ Pattern ${\cal D}$}
		\end{figure}
		\begin{figure}
		%\vspace{0.2in}
		\centerline{\psfig{figure=grid.7.E.ps,height=1.0in}}
                \caption{\label{fig:grid.7.E}$7 \times m$ Pattern ${\cal E}$}
		\end{figure}
		\begin{figure}
		%\vspace{0.2in}
		\centerline{\psfig{figure=grid.7.F.ps,height=1.0in}}
                \caption{\label{fig:grid.7.F}$7 \times m$ Pattern ${\cal F}$}
		\end{figure}

	        \begin{table}
		\begin{center}
		\begin{tabular}{|l|l|} \hline
		1 & ${\cal E'F'} \rightarrow {\cal BA'F}$ \\ \hline
		2 & ${\cal F} \rightarrow {\cal CD}$ \\ \hline
		3 & ${\cal CD} \rightarrow {\cal AEF}$ \\ \hline
		4 & ${\cal EF} \rightarrow {\cal B'AF'}$ \\ \hline
		5 & ${\cal F'} \rightarrow {\cal C'D'}$ \\ \hline
		6 & ${\cal C'D'} \rightarrow {\cal A'E'F'}$ \\ \hline
		\end{tabular}
		\end{center}
		\caption{\label{tab:7_by_rules}
			Rewrite rules for $7 \times m$ Grids}
		%\end{table}
	        %\begin{table}
		\begin{center}
		\begin{tabular}{|r|c|c|c|c|}\hline
		$m$ = & 6 & 7 & 8 & 9  \\ \hline
		String & 
			${\cal FA'BA'F}$ & 
			${\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}
	        \caption{\label{table:grid.7.m} 
			String Representations for $7 \times m$ Grids}
	        \end{table}

%	\subsection{$8 \times m$ Grids}
%
%	\hspace{1em}The work was going great until here.  At this point the
%	computation bogged down a lot, but that is what is to be
%	expected from an NP-Complete problem.   For the $8 \times m$
%	Grid there are several building blocks.  The first is the SMT
%	on an $8 \times 8$ grid which is given in
%	Figure~\ref{fig:grid.8.8}.  
%
%	After the $8 \times 8$,  all the other grids are built by
%	putting together grids of smaller sizes.  The $8 \times 9$ grid
%	is made up of 3 $8 \times 3$ grids linked together.  After that
%	it gets easy.  The $8 \times 10$ is made up of an $8 \times 8$
%	and an $8 \times 2$, the $8 \times 11$ is made up of and $8
%	\times 8$ and an $8 \times 3$.  This progression continues
%	through the $8 \times 17$ which is made up of an $8 \times 8$
%	and an $8 \times 9$.  After that it cycles back to an $8 \times
%	8$ and and $8 \times 10$ which is really and $8 \times 8$ and
%	an $8 \times 8$ and an $8 \times 2$.
%
%       		\begin{figure}[h]
%		\centerline{\psfig{figure=grid.8.8.ps,height=1.0in}}
%                \caption{\label{fig:grid.8.8}$8 \times 8$ }
%		\end{figure}
%
\section{Conclusions and Future Work}
	\label{sec:future_work}

	\hspace{1em}In this work we reviewed what is known about SMTs
	on grids and then presented results from
	PARSTEINER94~\cite{harris:dissertation,harris:pcosmt} which
	characterize SMTs for $3 \times m$ to $7 \times m$ grids.  The
	next obvious question is what is the characterization for an $8
	\times m$ grid, or an $n \times m$ grid?  Well, this is where
	things start getting nasty.  Even though PARSTEINER94 cuts the
	computation time of the previous best program for SMTs by an
	order of magnitude, the computation time for an NP-Hard problem
	blows up sooner or later, and $8 \times m$ is where we run into
	the computation wall.

	We have been able to make small chips into this wall though, 
	and have some
	results for $8 \times m$ grids.  The pattern for this seems to
	be based upon repeated use of the $8 \times 8$ grid which is
	shown in Figure~\ref{fig:grid.8.8}.  This grid solution seems
	to be combined with smaller $8 \times$ solutions in order to
	build larger solutions.  However, until better computational
	approaces are developed further characterizations of SMTs on
	grids will be very hard, and tedious.

       		\begin{figure}[h]
		\centerline{\psfig{figure=grid.8.8.ps,height=2.0in}}
                \caption{\label{fig:grid.8.8}$8 \times 8$ }
		\end{figure}

\addcontentsline{toc}{section}{References}
\quad
\baselineskip=12pt
\parindent=0pt
\bibliography{/users2/staff/fredh/papers/bibdir/steiner,/users2/staff/fredh/papers/bibdir/fredh}
\end{document}

