Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Geometric matching algorithms for two realistic terrains

Title
Geometric matching algorithms for two realistic terrains
Authors
Yoon, Sang DukKim, Min-GyuSon, WanbinAhn, Hee-Kap
POSTECH Authors
Ahn, Hee-Kap
Date Issued
Mar-2018
Publisher
ELSEVIER SCIENCE BV
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-infinity or the L-1 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-infinity metric. We also give a deterministic algorithm that computes an optimal translation of f with respect to g under L-1 metric. (C) 2018 Elsevier B.V. All rights reserved.
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-infinity or the L-1 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-infinity metric. We also give a deterministic algorithm that computes an optimal translation of f with respect to g under L-1 metric. (C) 2018 Elsevier B.V. All rights reserved.
Keywords
Piecewise linear techniques; Bivariate functions; Combinatorial structures; Deterministic algorithms; Geometric matching; Piecewise linear; Realistic terrains; Sub-domains; Tight bound; Geometry
URI
http://oasis.postech.ac.kr/handle/2014.oak/93998
DOI
10.1016/j.tcs.2018.01.011
ISSN
0304-3975
Article Type
Article
Citation
THEORETICAL COMPUTER SCIENCE, vol. 715, page. 60 - 70, 2018-03
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

 AHN, HEE KAP
Dept of Computer Science & Enginrg
Read more

Views & Downloads

Browse