Matching Polyhedral Terrains Using Overlays of
Envelopes |
| |
Authors: | Vladlen Koltun Carola Wenk |
| |
Affiliation: | (1) Computer Science Division, University of California, Berkeley, CA 94720-1776, USA;(2) Department of Computer Science, The University of Texas at San Antonio, 6900 N. Loop 1604 West, San Antonio, TX 78249-0667, USA |
| |
Abstract: | For a collection $\F$ of $d$-variate piecewise linear functions of
overall combinatorial complexity $n$, the lower envelope $\E(\F)$ of
$\F$ is the pointwise minimum of these functions. The minimization
diagram $\M(\F)$ is the subdivision of $\reals^d$ obtained by
vertically (i.e., in direction $x_{d+1}$) projecting $\E(\F)$. The overlay
$\O(\F,\G)$ of two such subdivisions $\M(\F)$ and $\M(\G)$ is their
superposition. We extend and improve the analysis of de Berg et al.
\cite{bgh-vdt3s-96} by showing that the combinatorial complexity of
$\O(\F,\G)$ is $\Omega(n^d \alpha^{2}(n))$ and $O(n^{d+\eps})$ for any
$\eps>0$ when $d \ge 2$, and $O(n^2 \alpha(n) \log n)$ when $d=2$. We also
describe an algorithm that constructs $\O(\F,\G)$ in this time.
We apply these results to obtain efficient general solutions to the
problem of matching two polyhedral terrains in higher dimensions under
translation. That is, given two piecewise linear terrains of combinatorial
complexity $n$ in $\reals^{d+1}$, we wish to find a translation of the
first terrain that minimizes its distance to the second, according to some
distance measure. For the perpendicular distance measure, which we adopt
from functional analysis since it is natural for measuring the similarity
of terrains, we present a matching algorithm that runs in time
$O(n^{2d+\eps})$ for any $\eps>0$. Sharper running time bounds are shown
for $d \le 2$. For the directed and undirected \Hd\ distance measures, we
present a matching algorithm that runs in time $O(n^{d^2+d+\eps})$ for any
$\eps>0$. |
| |
Keywords: | Arrangements Overlays of envelopes Polyhedral terrains Matching |
本文献已被 SpringerLink 等数据库收录! |
|