Computing the distance between piecewise-linear bivariate functions

Guillaume Moroz; Boris Aronov

doi:10.1145/2847257

Computing the distance between piecewise-linear bivariate functions

Guillaume Moroz, Boris Aronov

Research output: Contribution to journal › Article › peer-review

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)². 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²) arithmetic operations to compute this distance.We show that it is possible to compute it in O(nlog⁴ 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	https://doi.org/10.1145/2847257
State	Published - Feb 2016

Keywords

Multipoint evaluation
Piecewise-linear function
Polyhedral terrain

ASJC Scopus subject areas

Mathematics (miscellaneous)

Access to Document

10.1145/2847257

Cite this

@article{91420ecb3db04ed9ba6e6a5f0257792f,

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, 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 Θ (n2) arithmetic operations to compute this distance.We show that it is possible to compute it in O(nlog4 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.",

keywords = "Multipoint evaluation, Piecewise-linear function, Polyhedral terrain",

author = "Guillaume Moroz and Boris Aronov",

note = "Publisher Copyright: {\textcopyright} 2016 ACM.",

year = "2016",

month = feb,

doi = "10.1145/2847257",

language = "English (US)",

volume = "12",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - Computing the distance between piecewise-linear bivariate functions

AU - Moroz, Guillaume

AU - Aronov, Boris

PY - 2016/2

Y1 - 2016/2

N2 - 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 Θ (n2) arithmetic operations to compute this distance.We show that it is possible to compute it in O(nlog4 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.

AB - 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 Θ (n2) arithmetic operations to compute this distance.We show that it is possible to compute it in O(nlog4 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.

KW - Multipoint evaluation

KW - Piecewise-linear function

KW - Polyhedral terrain

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

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

U2 - 10.1145/2847257

DO - 10.1145/2847257

M3 - Article

AN - SCOPUS:84964424955

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 3

ER -

Computing the distance between piecewise-linear bivariate functions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this