Matching Terrains under a Linear Transformation

Pankaj K. Agarwal; Boris Aronov; Marc van Kreveld; Maarten Löffler; Rodrigo I. Silveira

Matching Terrains under a Linear Transformation

Pankaj K. Agarwal, Boris Aronov, Marc van Kreveld, Maarten Löffler, Rodrigo I. Silveira

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

Abstract

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+$-approximation algorithm for minimizing the area in between that runs in $O(n / 1/2)$ time, for any fixed $epsilon > 0$.

Original language	English
Title of host publication	Proc. 25th European Workshop on Computational Geometry
Pages	109-112
Number of pages	4
Publication status	Published - 2009

Keywords

CG, GIS, TIN

Cite this

@inproceedings{1555231de05d4df5ad4c367103630757,

title = "Matching Terrains under a Linear Transformation",

abstract = "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\textasciicircum{}4/3 polylog n)\$ 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 \$epsilon > 0\$.",

keywords = "CG, GIS, TIN",

author = "Agarwal, \{Pankaj K.\} and Boris Aronov and Kreveld, \{Marc van\} and Maarten L{\"o}ffler and Silveira, \{Rodrigo I.\}",

year = "2009",

language = "English",

pages = "109--112",

booktitle = "Proc. 25th European Workshop on Computational Geometry",

}

TY - GEN

T1 - Matching Terrains under a Linear Transformation

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Kreveld, Marc van

AU - Löffler, Maarten

AU - Silveira, Rodrigo I.

PY - 2009

Y1 - 2009

N2 - 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+$-approximation algorithm for minimizing the area in between that runs in $O(n / 1/2)$ time, for any fixed $epsilon > 0$.

AB - 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+$-approximation algorithm for minimizing the area in between that runs in $O(n / 1/2)$ time, for any fixed $epsilon > 0$.

KW - CG, GIS, TIN

M3 - Conference contribution

SP - 109

EP - 112

BT - Proc. 25th European Workshop on Computational Geometry

ER -

Matching Terrains under a Linear Transformation

Abstract

Keywords

Fingerprint

Cite this