To access the full text documents, please follow this link: http://hdl.handle.net/2117/23696

Computing correlation between piecewise-linear functions
Agarwal, Pankaj; Aronov, Boris; Van Kreveld, Matias; Löffler, Maarten; Silveira, Rodrigo Ignacio
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
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}\operatorname{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+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional
Computational geometry
piecewise-linear function
polyhedral terrain
similarity
approximation algorithm
correlation
Geometria computacional
68U05
68Q25
68W25
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Hurtado Díaz, Fernando Alfredo; Korman Cozzetti, Matías; Van Kreveld, Matias; Löffler, Maarten; Sacristán Adinolfi, Vera; Silveira, Rodrigo Ignacio; Speckmann, Bettina
Speckmann, Bettina; Silveira, Rodrigo Ignacio; Aronov, Boris; Buchin, Kevin; Buchin, Maike; Jansen, Bart; De Jong, Tom; Kreveld, Marc van; Loffler, Maarten; Luo, Jun
Buchin, Kevin; Kostitsyna, Irina; Löffler, Maarten; Silveira, Rodrigo Ignacio
Löffler, Maarten; Saumell, Maria; Silveira, Rodrigo Ignacio
 

Coordination

 

Supporters