Computing the discrete fréchet distance with imprecise input

Heekap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine E. Vigneron

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

We consider the problem of computing the discrete Frechet distance between two polyg- onal 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 2n 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 pla- nar case with running time O(mnlog 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∞ distance, we give an O(dmnlog(dmn))-time algorithm. We also give effcient 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). © 2012 World Scientific Publishing Company.
Original languageEnglish (US)
Pages (from-to)27-44
Number of pages18
JournalInternational Journal of Computational Geometry & Applications
Volume22
Issue number01
DOIs
StatePublished - Sep 12 2012

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computational Mathematics
  • Geometry and Topology
  • Theoretical Computer Science
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Computing the discrete fréchet distance with imprecise input'. Together they form a unique fingerprint.

Cite this