A Subquadratic Algorithm for Computing the L1-Distance Between Two Terrains

We study the problem of computing the L1-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain M ⊂ R2, that is, computing the quantity ∥f-g∥1 = ∫M|f(x, y)-g(x, y)| dx dy. If f and g are defined by linear interpolation over triangulations Tf and Tg, respectively, of M with a total of n triangles, we show that ∥f - g∥1 can be computed in Õ(nα) time, where α = max{(ω + 1)/2, 8/5}, ω is the matrix multiplication exponent, and Õnotation hides factors of the form nϵ for any ϵ > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of Tf and Tg is κ, then the runtime of our algorithm is Õ(κα-1n2-α).

Duke Scholars

Author Pankaj K. Agarwal Computer Science