Math @ Duke

Publications [#235359] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Van Kreveld, M; Löffler, M; Silveira, RI, Computing correlation between piecewiselinear functions,
SIAM Journal on Computing, vol. 42 no. 5
(December, 2013),
pp. 18671887, ISSN 00975397 [doi]
(last updated on 2018/05/26)
Abstract: We study the problem of computing correlation between two piecewiselinear 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(n 4/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 + log 2 (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. © 2013 Society for Industrial and Applied Mathematics.


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

