Unstructured (triangulated) grids have computational advantages over rectangular ones in three common situations:

- When the number of grid points can be substantially reduced by putting them on an irregular grid. This situation corresponds to irregular distribution of details in the propagation medium.
- When the computational domain has irregular boundaries. One possible kind of boundary corresponds to geological interfaces and seismic reflector surfaces Wiggins et al. (1993). Another type of irregular boundary, in application to traveltime computations, is that of seismic rays. The method of bounding the numerical eikonal solution by ray envelopes has been introduced recently by Abgrall and Benamou (1996).
- When the grid itself needs to be dynamically updated to maintain a certain level of accuracy in the computation.

Figure 5

Figure 5 shows a comparison between first-arrival traveltime computations in regularly gridded and triangulated Marmousi models. The two results match each other within the first-order accuracy of the fast marching method. However, the cost of the triangulated computation has been greatly reduced by constraining the number of nodes.

Computational aspects of triangular grid generation are outlined in Appendix A. A three-dimensional application would follow the same algorithmic patterns.

10/9/1997