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.