Computing the discrete Fréchet distance with imprecise input

Hee Kap Ahn*, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

We consider the problem of computing the discrete Fréchet 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 2O(d2)m2n 2 log2(mn) the Fréchet 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) + (m2 + n2)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(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the Fréchet distance upper bound, as well as the smallest possible Fréchet 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).

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages422-433
Number of pages12
EditionPART 2
DOIs
StatePublished - Dec 1 2010
Event21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of
Duration: Dec 15 2010Dec 17 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6507 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
CountryKorea, Republic of
CityJeju Island
Period12/15/1012/17/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this