3530 articles – 5253 references  [version française]

inria-00608255, version 2

Computing the Distance between Piecewise-Linear Bivariate Functions

Guillaume Moroz () 1, Boris Aronov 2

SODA - Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms - 2012 (2012)

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=\sqrt{\iint_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 $\Theta(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.

  • 1:  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2:  Polytechnic institute of New York University (NYU-Poly)
  • New York University
  • Domain : Computer Science/Computational Geometry
    Computer Science/Symbolic Computation
    Computer Science/Computational Complexity
  • Keywords : piecewise-linear functions – integration – $L^2$-norm – multi-point evaluation – algebraic methods
  • Available versions :  v1 (2011-07-12) v2 (2011-07-13)
 
  • inria-00608255, version 2
  • http://hal.inria.fr/inria-00608255
  • oai:hal.inria.fr:inria-00608255
  • From: Guillaume Moroz <>
  • Submitted on: Tuesday, 12 July 2011 22:58:11
  • Updated on: Wednesday, 6 February 2013 15:43:11