Computing Correlation between Piecewise-Linear Functions
We study the problem of matching two polyhedral terrains, where one can be changed vertically by a linear transformation of the third coordinate (scaling and translation). We give an algorithm that minimizes the maximum distance over all linear transformations in O(n4/3polylogn) expected time. We also study matching two 1-dimensional terrains, and give a (1 + ϵ)-approximation algorithm for minimizing the area in between that runs in O(n/ϵ1/2) time, for any fixed ϵ > 0.
keywords: Computational Geometry, Geographical Information Analysis, Terrains
Journal Article (peer-reviewed)
Boris Aronov, Maarten Löffler, Marc van Kreveld, Pankaj K. Agarwal, Rodrigo I. Silveira
Computing Correlation between Piecewise-Linear Functions
SIAM Journal on Computing
42, 5, 1867–1887, 2013
Conference Proceedings (peer-reviewed)
Boris Aronov, Maarten Löffler, Marc van Kreveld, Pankaj K. Agarwal, Rodrigo I. Silveira
Computing Similarity between Piecewise-Linear Functions
Proc. 26th Symposium on Computational Geometry
375–383, 2010
Workshop or Poster (weakly reviewed)
Boris Aronov, Maarten Löffler, Marc van Kreveld, Pankaj K. Agarwal, Rodrigo I. Silveira
Matching Terrains under a Linear Transformation
Proc. 25th European Workshop on Computational Geometry
109–112, 2009
back to list
