We apply Ordinary Kriging to predict 75,000 terrain survey data from a randomly sampled subset of < 2500 observations. Since such a Kriging prediction requires a considerable amount of CPU time, we aim to reduce its computational cost. In a conventional approach, the cost of the Kriging analysis would be dominated by the optimization routine required to find the maximum likelihood, which provides an estimate of the correlation ranges. We propose to transform the optimization problem to the frequency domain, such that the cost of the optimization is now dominated by that of a single Fourier transform required to find the power spectrum of the observations, as a result of which the computational cost is now virtually independent of the number of optimization steps. For the present application, we find that the proposed approach is as accurate as the conventional approach for a sample size of 100 or more. The CPU time increases with the number of optimization steps for the conventional approach, while it is virtually constant for the proposed approach.