Computing similarity between piecewise-linear functions

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D-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 study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1+ε)-approximation algorithm for minimizing the area that runs in O(n/√ε) time, for any fixed ε > 0. The (1 + ε)-approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/ε2) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
    Number of pages9
    StatePublished - 2010
    Event26th Annual Symposium on Computational Geometry, SoCG 2010 - Snowbird, UT, United States
    Duration: Jun 13 2010Jun 16 2010

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry


    Other26th Annual Symposium on Computational Geometry, SoCG 2010
    Country/TerritoryUnited States
    CitySnowbird, UT


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

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics


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

    Cite this