Using both P and S arrival time information, 41108 events in the International Seismological Centre catalog for the years 1964 to 1987 are relocated relative to the IASP91 velocity model. When plotted as bottoming point averages, the resulting IASP91 P and S arrival time residuals show coherent patterns as a function of geographic location. An iterative l(p) residual norm minimization algorithm is used to estimate the set of P and S velocity variations as well as the earthquake relocation and seismographic station parameters which best explain the travel time residuals. Both the P and S models of lateral heterogeneity contain prominent circum-Pacific low velocities. Coherent high-velocity features are seen below South America, Borneo, Tonga-Fiji, the Marianas, and the northern Kuriles.