DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn H.-K | - |
dc.contributor.author | Christian Knauer | - |
dc.contributor.author | Marc Scherfenberg | - |
dc.contributor.author | Lena Schlipf | - |
dc.contributor.author | Antoine Vigneron | - |
dc.date.accessioned | 2016-04-01T07:35:35Z | - |
dc.date.available | 2016-04-01T07:35:35Z | - |
dc.date.created | 2011-03-24 | - |
dc.date.issued | 2010-12 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.other | 2010-OAK-0000023008 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/26668 | - |
dc.description.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)(d(2))m(2)n(2) log(2)(mn) the Frechet distance lower bound 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(2) (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 Lco distance, we give an O(dninlog(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the Frechet distance upper bound, as well as the smallest possible Frechet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. 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). | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | Springer | - |
dc.relation.isPartOf | LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.title | Computing the Discrete Frechet Distance with Imprecise Input | - |
dc.type | Article | - |
dc.contributor.college | 컴퓨터공학과 | - |
dc.identifier.doi | 10.1007/978-3-642-17514-5_36 | - |
dc.author.google | Ahn H.-K., Knauer C., Scherfenberg M., Schlipf L., Vigneron A. | - |
dc.relation.volume | 6507 | - |
dc.relation.startpage | 422 | - |
dc.relation.lastpage | 433 | - |
dc.contributor.id | 10152366 | - |
dc.relation.journal | LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.relation.sci | SCIE | - |
dc.collections.name | Conference Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | LECTURE NOTES IN COMPUTER SCIENCE, v.6507, pp.422 - 433 | - |
dc.identifier.wosid | 000296483600036 | - |
dc.date.tcdate | 2019-02-01 | - |
dc.citation.endPage | 433 | - |
dc.citation.startPage | 422 | - |
dc.citation.title | LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.citation.volume | 6507 | - |
dc.contributor.affiliatedAuthor | Ahn H.-K | - |
dc.identifier.scopusid | 2-s2.0-78650861075 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 2 | - |
dc.type.docType | Proceedings Paper | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.