The data domain is defined as the entire space we need to cover with the traveltime map. For example, in the 2-D case it becomes a planar surface and, in the 3-D case, it becomes a volume. We intend to fill the data with geometrical shapes and to interpolate the traveltime field in the interior of each such simplex from the data at the corners.

Our choice is to use a triangle as a 2-D simplex, or a tetrahedron as a 3-D simplex, because those are the most easily generated geometrical shapes that enable us to cover the entire data domain.

The triangulation method we use has to follow smoothly from ray to ray the
surface generated by the expansion in the take-off angle direction and to
avoid any artificial surface angularity. Therefore, we want to
generate the simplex that is the most isometrical (``fat'' triangles or
tetrahedra) and to avoid the elongated ones (that is, to maximize the
minimum angle in each simplex). We can achieve this by using *Delaunay
triangulation,* which ensures the best result with respect to this
criterion (see, for example, O'Rourke (1993)).

In the Delaunay method, simplexes are built so that no point of the
triangulated mesh falls inside any of the circles (in two dimensions) or
spheres (in three dimensions) that pass through all three (in the
2-D case) or four points (in the 3-D case) of any other simplex in the
triangulation. Such a triangulation method is *constrained* if it only
uses the actual points in the data set, without adding other points to
maximize the angles of the triangles or tetrahedra.

We have employed constrained Delaunay triangulation in this particular application in order to preserve all the features of the input data and not increase the amount of computing time.

Once we define the simplex, we can compute traveltimes, and possibly amplitudes, at each grid point inside each simplex, taking either a linear shape (a plane) or a more complex shape (for example a polynomial function) from the values at the edges.

10/9/1997