Geometric matching algorithms for two realistic terrains

We consider a geometric matching of two realistic terrains, each of which is modeled as a piecewise-linear bivariate function. For two realistic terrains f and g where the domain of g is relatively larger than that of f, we seek to find a translated copy f′ of f such that the domain of f′ is a sub-d...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2018-03, Vol.715, p.60-70
Main Authors: Yoon, Sang Duk, Kim, Min-Gyu, Son, Wanbin, Ahn, Hee-Kap
Format: Article
Language:English
Subjects:
Geometric matching algorithm
Piecewise-linear bivariate function
Realistic terrain
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a geometric matching of two realistic terrains, each of which is modeled as a piecewise-linear bivariate function. For two realistic terrains f and g where the domain of g is relatively larger than that of f, we seek to find a translated copy f′ of f such that the domain of f′ is a sub-domain of g and the L∞ or the L1 distance of f′ and g restricted to the domain of f′ is minimized. In this paper, we show a tight bound on the number of different combinatorial structures that f and g can have under translation in their projections on the xy-plane. We give a deterministic algorithm and a randomized one that compute an optimal translation of f with respect to g under L∞ metric. We also give a deterministic algorithm that computes an optimal translation of f with respect to g under L1 metric.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2018.01.011