Activity‎ > ‎

GAIA Seminar - Boris Aronov(Polytechnic Institute of NYU)

posted Dec 4, 2012, 6:26 PM by Jihye Jung   [ updated Dec 4, 2012, 6:28 PM ]
- Title : Computing the Distance between Piecewise- Linear Bivariate Functions


- Speaker :Boris Aronov(Polytechnic Institute of NYU)

- Date & Time : 12 December(Wed), 2012 (14p.m. - 16p.m.)
- Place : Math Science building room 208
- 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 L_2-norm, that is ||F-G||=sqrt(integral(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 naive 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 log 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 and discuss several generalizations and extensions.

This is joint work with Guillaume Moroz from INRIA Grand-Est, Nancy, France.


- Contact: Hee-Kap Ahn (, Tel. 279-2387

Jihye Jung,
Dec 4, 2012, 6:29 PM