Matching Terrains under a Linear Transformation

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/3 polylog n) expected time. We also study matching two 1-dimensional terrains, and give a (1+epsilon)-approximation algorithm for minimizing the area in between that runs in O(n / root epsilon) time, for any fixed epsilon > 0.

slides

Conference Proceedings

Conference Proceedings (non-competitive)

back to list