\section*{Mesh Generation}

High-quality unstructured meshes are difficult to generate, but not because
it is difficult to generate an unstructured mesh.
There are simple techniques for
triangulating an arbitrary two-dimensional region, and although
tetrahedralizing a three-dimensional region is much more complicated, there
are straightforward techniques for doing so.  A good survey of mesh
triangulation methods in two and three dimensions is provided by
Bern and Eppstein~\cite{bern92}.

The real difficulty, though, is that a mesh generator should avoid producing
elements with large aspect ratios --- ``skinny'' triangles and tetrahedra,
so to speak --- because angles close to $180^\circ$ cause a large
discretization error~\cite{babuska76}, and very small angles cause the
stiffness matrix ${\bf K}$ to be ill-conditioned~\cite{carey}.
This constraint is difficult to maintain in a mesh that must conform to
an object with a complicated shape.

Archimedes includes a two-dimensional mesh generator named
Triangle~\cite{shewchuk96b} that triangulates
complex geometries with high-quality elements, and furthermore allows the
density of elements to vary and be controlled by the user, as was necessary
to generate Figure~\ref{unstruc}.
The meshing algorithm is due to Ruppert~\cite{ruppert95}, who
has proven that his algorithm generates meshes
whose triangles have angles bounded between
$20^\circ$ and $140^\circ$
(except where there are input angles smaller than $20^\circ$; these cannot be
improved).
Archimedes currently has
only rudimentary 3D mesh generation; work on an effective 3D mesh
generator is in progress.

\begin{figure}
\centerline{\epsfxsize=4in \epsfbox{guitar2.2.ele.eps}}
\caption{\label{refine} Refinement of the original mesh.}
\end{figure}

The mesh generation algorithm serves another purpose.
After the mesh is generated and the simulation completed, the
approximate solution might not be
as close to the exact solution as desired.  A better solution
can be found by refining the mesh and repeating the solution process.
A mesh is {\em refined} by dividing some or all of its elements
into a larger number
of smaller elements, as in Figure \ref{refine}.  As the mesh is refined,
the approximate solution
converges to the exact solution $u$.
Numerical analysts have developed
{\em a priori error estimates} that show that the {\em discretization error}
is reduced as the size of the largest edge is reduced.
However, as we have explained, a uniform density of elements
throughout the domain is not always desirable.
Hence, there are also {\em a posteriori error estimates}, which estimate the
discretization error on each element
after the simulation, thereby providing a guide to refinement.
Figure~\ref{refine} was generated from Figure \ref{mesh}
as follows:
Archimedes solved a heat conduction problem on the original mesh,
and generated {\em a posteriori} error estimates on each
element of the mesh.  Based on the error estimates, it determined a maximum
desired triangle area on each element.  Archimedes' mesh generator refined
the existing mesh so that no triangle has area greater
than the maximum allowed.
