Computing the distance between piecewise-linear bivariate functions

Guillaume Moroz; Boris Aronov

doi:10.1137/1.9781611973099.27

Computing the distance between piecewise-linear bivariate functions

Guillaume Moroz, Boris Aronov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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₂-norm, that is ||f - g|| ₂ = √∫∫_M(f - g)². 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²) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log⁴ 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	https://doi.org/10.1137/1.9781611973099.27
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/Territory	Japan
City	Kyoto
Period	1/17/12 → 1/19/12

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1137/1.9781611973099.27

Cite this

Computing the distance between piecewise-linear bivariate functions. / Moroz, Guillaume; Aronov, Boris.
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, 2012. p. 288-293 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Moroz, G & Aronov, B 2012, Computing the distance between piecewise-linear bivariate functions. in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 288-293, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 1/17/12. https://doi.org/10.1137/1.9781611973099.27

@inproceedings{9369d7b9aad14bd381593bae64dd2f83,

title = "Computing the distance between piecewise-linear bivariate functions",

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 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, while g is defined over another such triangulation, the obvious na{\"i}ve algorithm requires Θ(n2) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log4 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.",

author = "Guillaume Moroz and Boris Aronov",

year = "2012",

doi = "10.1137/1.9781611973099.27",

language = "English (US)",

isbn = "9781611972108",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "288--293",

booktitle = "Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012",

note = "23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 ; Conference date: 17-01-2012 Through 19-01-2012",

}

TY - GEN

T1 - Computing the distance between piecewise-linear bivariate functions

AU - Moroz, Guillaume

AU - Aronov, Boris

PY - 2012

Y1 - 2012

N2 - 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 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, while g is defined over another such triangulation, the obvious naïve algorithm requires Θ(n2) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log4 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.

AB - 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 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, while g is defined over another such triangulation, the obvious naïve algorithm requires Θ(n2) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log4 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.

UR - http://www.scopus.com/inward/record.url?scp=84860166197&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860166197&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.27

DO - 10.1137/1.9781611973099.27

M3 - Conference contribution

AN - SCOPUS:84860166197

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 288

EP - 293

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

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

Y2 - 17 January 2012 through 19 January 2012

ER -

Computing the distance between piecewise-linear bivariate functions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this