- 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 (heekap@postech.ac.kr, Tel. 279-2387 |
Activity >
