Article

Cited *0* time in
Cited *0* time in

Metadata Downloads

Geometric matching algorithms for two realistic terrains

- Title
- Geometric matching algorithms for two realistic terrains

- Authors
- Yoon, Sang Duk; Kim, Min-Gyu; Son, Wanbin; Ahn, 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

- 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.

- AHN, HEE KAP
- Dept of Computer Science & Enginrg

OAK

library@postech.ac.kr
*Tel: 054-279-2548*

Copyrights © by 2017 Pohang University of Science and Technology All right reserved.