Maarten Löffler

We study the problem of computing the similarity of two
piecewise-linear bivariate functions defined over a common domain, where
the surfaces they define in 3D---polyhedral terrains---can be
transformed vertically by a linear transformation of the third
coordinate (scaling and translation). We give an algorithm that
minimizes the maximum vertical distance between the graphs
of the two functions, over all linear
transformations, in O(*n*^{4/3} polylog *n*) expected
time, where *n* is the total number of vertices in the graphs of the
two functions. We also study the computation of similarity of two
univariate or bivariate functions by minimizing the area or volume
in between their graphs. For univariate functions we give a
(1+ε)-approximation algorithm for minimizing the area that runs
in O(*n*/ε^{1/2}) time, for any fixed ε>0. The
(1+ε)-approximation algorithm for the bivariate version, where volume
is minimized, runs in O(*n*/ε^{2}) time, for any fixed ε>0,
provided the two functions are defined over the same triangulation
of their domain.