Computing correlation between piecewise-linear functions

Pankaj K. Agarwal, Boris Aronov, Marc Van Kreveld, Maarten Löffler, Rodrigo I. Silveira

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions - polyhedral terrains - can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4/3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a (1 + ε)-approximation algorithm that runs in O(n(1 + log2(1/ε))) expected time for any fixed ε > 0. The (1 + ε)-approximation algorithm for bivariate functions runs in O(n/ε) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain.

    Original languageEnglish (US)
    Pages (from-to)1867-1887
    Number of pages21
    JournalSIAM Journal on Computing
    Volume42
    Issue number5
    DOIs
    StatePublished - 2013

    Keywords

    • Approximation algorithm
    • Correlation
    • Piecewise-linear function
    • Polyhedral terrain
    • Similarity

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

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

    Cite this