Computing the distance between piecewise-linear bivariate functions

Guillaume Moroz, Boris Aronov

    Research output: Chapter in Book/Report/Conference proceedingConference 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 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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    PublisherAssociation for Computing Machinery
    Pages288-293
    Number of pages6
    ISBN (Print)9781611972108
    DOIs
    StatePublished - 2012
    Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
    Duration: Jan 17 2012Jan 19 2012

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    CountryJapan
    CityKyoto
    Period1/17/121/19/12

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Computing the distance between piecewise-linear bivariate functions'. Together they form a unique fingerprint.

  • Cite this

    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 (pp. 288-293). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.27