Math @ Duke

Publications [#235525] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Kreveld, MV; Löffler, M; Silveira, RI, Computing similarity between piecewiselinear functions,
Proceedings of the Annual Symposium on Computational Geometry
(2010),
pp. 375383 [doi]
(last updated on 2018/10/16)
Abstract: We study the problem of computing the similarity between two piecewiselinear bivariate functions defined over a common domain, where the surfaces they define in 3Dpolyhedral terrainscan 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

