TY - GEN
T1 - Computing similarity between piecewise-linear functions
AU - Agarwal, Pankaj K.
AU - Aronov, Boris
AU - Van Kreveld, Marc
AU - Löffler, Maarten
AU - Silveira, Rodrigo I.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Piecewise-linear function
KW - Polyhedral terrain
KW - Randomized algorithm
KW - Similarity
UR - http://www.scopus.com/inward/record.url?scp=77954897132&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954897132&partnerID=8YFLogxK
U2 - 10.1145/1810959.1811020
DO - 10.1145/1810959.1811020
M3 - Conference contribution
AN - SCOPUS:77954897132
SN - 9781450300162
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 375
EP - 383
BT - Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
T2 - 26th Annual Symposium on Computational Geometry, SoCG 2010
Y2 - 13 June 2010 through 16 June 2010
ER -