A dynamic programming approach to first arrival traveltime computation in media with arbitrarily distributed velocities

Abstract Curved-ray tomographic traveltime inversion, reverse-time migration and various other seismic modeling applications require the calculation of traveltime and raypath information throughout a two- or three-dimensional medium. When arbitrary velocity distributions and curved rays are involved, traditional ray shooting or bending procedures can be time consuming and error prone. A two-dimensional dynamic programming traveltime computation technique, based upon Fermat's principle, uses simple calculus techniques and a systematic mapping scheme to determine first-arrival times on a uniform grid, given an arbitrary, discrete velocity distribution. It accurately handles large contrast, discontinuous velocity distributions, including those that generate caustics. First arrival seismic energy can travel either as transmitted waves, diffracted waves, or headwaves, and this technique models all types.The traveltime computations begin with starting values computed near the source location. Then, the mapping systematically steps through the grid, where each new arrival time is calculated using two previously computed 'neighbor' traveltimes. We present two mapping procedures, a brute force approach that advances across the grid one column (or row) at a time and a more natural approach that computes times along expanding rectangles.Isotime lines within the traveltime grid represent wavefronts, and seismic raypaths can be numerically computed through the traveltime grid as orthogonal trajectories to the wavefronts. Such a forward model was used in a curved-raypath tomographic inversion program to successfully invert a physical model crosshole data set. The traveltime computation algorithm also performed successfully on several difficult velocity models. On a discontinuous, large contrast velocity model, traveltimes agreed to within 0.12 percent with those of an accurate ray-tracing program.