Geometric matching algorithms for two realistic terrains
SCIE
SCOPUS
- Title
- Geometric matching algorithms for two realistic terrains
- Authors
- Yoon, Sang Duk; Kim, Min-Gyu; Son, Wanbin; Ahn, Hee-Kap
- Date Issued
- 2018-03
- 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.
- Keywords
- Piecewise linear techniques; Bivariate functions; Combinatorial structures; Deterministic algorithms; Geometric matching; Piecewise linear; Realistic terrains; Sub-domains; Tight bound; Geometry
- URI
- https://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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.