## Abstract

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M, induced by the L2 norm-that is, ∥ f - g∥2 = √ ∫M( f - g)^{2}. If f is defined by linear interpolation over a triangulation of M with n triangles and g is defined over another such triangulation, the obvious naive algorithm requires Θ (n^{2}) arithmetic operations to compute this distance.We show that it is possible to compute it in O(nlog^{4} nlog log n) arithmetic operations by reducing the problem to multipoint evaluation of a certain type of polynomials. We also present several generalizations and an application to terrain matching.

Original language | English (US) |
---|---|

Article number | 3 |

Journal | ACM Transactions on Algorithms |

Volume | 12 |

Issue number | 1 |

DOIs | |

State | Published - Feb 2016 |

## Keywords

- Multipoint evaluation
- Piecewise-linear function
- Polyhedral terrain

## ASJC Scopus subject areas

- Mathematics (miscellaneous)