### Abstract

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M. We focus on the distance induced by the L_{2}-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, while g is defined over another such triangulation, the obvious naïve algorithm requires Θ(n^{2}) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log^{4} n) arithmetic operations, by reducing the problem to multi-point evaluation of a certain type of polynomials. We also present an application to terrain matching.

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

Title of host publication | Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |

Publisher | Association for Computing Machinery |

Pages | 288-293 |

Number of pages | 6 |

ISBN (Print) | 9781611972108 |

DOIs | |

State | Published - 2012 |

Event | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan Duration: Jan 17 2012 → Jan 19 2012 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |
---|---|

Country | Japan |

City | Kyoto |

Period | 1/17/12 → 1/19/12 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Computing the distance between piecewise-linear bivariate functions'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012*(pp. 288-293). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.27