Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875601 | Theoretical Computer Science | 2018 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sang Duk Yoon, Min-Gyu Kim, Wanbin Son, Hee-Kap Ahn,