Computing Correlation between Piecewise-Linear Functions

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(n^4/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

http://dx.doi.org/10.1137/120900708

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

http://dl.acm.org/authorize?351443

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