Computing the Distance between Piecewise-Linear Bivariate Functions

Details Computing the Distance between Piecewise-Linear Bivariate Functions Computing the Distance between Piecewise-Linear Bivariate Functions

2011-07-12

arxiv.org/abs/1107.2312v2

Computer Science

Computational Geometry

Scientific paper

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\"ive 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.

Affiliated with

Also associated with

No associations

Rating

Computing the Distance between Piecewise-Linear Bivariate Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the Distance between Piecewise-Linear Bivariate Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Distance between Piecewise-Linear Bivariate Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-565589