Open Access System for Information Sharing

Login Library

 

Article
Cited 2 time in webofscience Cited 8 time in scopus
Metadata Downloads

COMPUTING THE DISCRETE FRECHET DISTANCE WITH IMPRECISE INPUT

Title
COMPUTING THE DISCRETE FRECHET DISTANCE WITH IMPRECISE INPUT
Authors
Ahn, HKKnauer, CScherfenberg, MSchlipf, LVigneron, A
POSTECH Authors
Ahn, HK
Date Issued
Feb-2012
Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
Abstract
We consider the problem of computing the discrete Frechet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2(O(d2))m(2)n(2)log(2)(mn) the minimum Frechet distance between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log(3)(mn) + (m(2)+n(2)) log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L-infinity distance, we give an O(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the maximum Frechet distance, as well as the minimum and maximum Frechet distance under translation. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).
Keywords
Shape matching; Frechet distance; imprecise input; GEOMETRIC OPTIMIZATION; CURVES; POINTS
URI
http://oasis.postech.ac.kr/handle/2014.oak/15908
DOI
10.1142/S0218195912600023
ISSN
0218-1959
Article Type
Article
Citation
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, vol. 22, no. 1, page. 27 - 44, 2012-02
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