Computing the Distance between Piecewise-Linear Bivariate Functions

Guillaume Moroz 1 Boris Aronov 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Type de document :
Communication dans un congrès
SODA - Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms - 2012, Jan 2012, Kyoto, Japan. SIAM, 2012
Liste complète des métadonnées


https://hal.inria.fr/inria-00608255
Contributeur : Guillaume Moroz <>
Soumis le : mardi 12 juillet 2011 - 22:58:11
Dernière modification le : mardi 25 octobre 2016 - 16:58:10
Document(s) archivé(s) le : lundi 5 décembre 2016 - 00:28:45

Fichiers

integral.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00608255, version 2
  • ARXIV : 1107.2312

Collections

Citation

Guillaume Moroz, Boris Aronov. Computing the Distance between Piecewise-Linear Bivariate Functions. SODA - Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms - 2012, Jan 2012, Kyoto, Japan. SIAM, 2012. <inria-00608255v2>

Partager

Métriques

Consultations de
la notice

404

Téléchargements du document

190