To map a terrain, we measure elevations at different spatial locations and then interpolate the resulting values. Usually, the measurement locations are used to triangulate the area. Then, on each of the resulting triangles, we perform linear interpolation. This is always possible: from the three linear equations corresponding to three known elevations at the three vertices, we can always find three coefficients a0, a1, and a2, which give the interpolated value y = a0 + a1 • x1 + a2 • x2.
When we have two maps of the same area, it is desirable to gauge how close these maps are, for example, by computing the L2-difference between the two piecewise-linear functions. If each triangulation uses n triangles, then we can compute the overlay of the two triangulations, and compute the L2-difference as the sum of integrals over all n2 triangles from the overlay. However, for large n, this may be too time-consuming. The authors show that the computation of this L2-difference can be made much faster, in time O(n • log4(n)), by using a fast multi-point evaluation algorithm for certain polynomials.
While for these polynomials, the fast multi-point evaluation algorithm is new, such algorithms are well known for many other polynomials: for example, the fast Fourier transform algorithm is, in effect, a fast multi-point evaluation for an appropriate polynomial. In summary, the authors’ novel state-of-the-art algorithm provides a drastic speed-up for the practical important problem of measuring distance between several maps of the same terrain.
