Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Computing correlation between piecewise-linear functions

Autor
Agarwal, P.K.; Aronov, B.; Van Kreveld, M.; Löffler, M.; Silveira, R.I.
Tipus d'activitat
Article en revista
Revista
SIAM journal on computing
Data de publicació
2013
Volum
42
Número
5
Pàgina inicial
1867
Pàgina final
1887
DOI
https://doi.org/10.1137/120900708 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/23696 Obrir en finestra nova
URL
http://epubs.siam.org/doi/abs/10.1137/120900708 Obrir en finestra nova
Resum
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(n^{4/3}\op...
Citació
Agarwal, P.K. [et al.]. Computing correlation between piecewise-linear functions. "SIAM journal on computing", 2013, vol. 42, núm. 5, p. 1867-1887.
Paraules clau
approximation algorithm, correlation, piecewise-linear function, polyhedral terrain, similarity
Grup de recerca
CGA -Computational Geometry and Applications

Participants

  • Agarwal, Pankaj  (autor)
  • Aronov, Boris  (autor)
  • Van Kreveld, Matias  (autor)
  • Löffler, Maarten  (autor)
  • Silveira, Rodrigo Ignacio  (autor)