A finite-difference method for computing the first arrival traveltimes by solving the Eikonal equation in the celerity domain has been developed. This algorithm incorporates the head and diffraction wave. We also adapt a fast sweeping method, which is extremely simple to implement in any number of dimensions, to obtain accurate first arrival times in complex velocity models. The method, which is stable and computationally efficient, can handle instabilities due to caustics and provide head waves traveltimes. Numerical examples demonstrate that the celerity-domain Eikonal solver provides accurate first arrival traveltimes. This new method is three times accurate more than the 2nd-order fast marching method in a linear velocity model with the same spacing.