An improved approximation algorithm for the discrete Fréchet distance

Timothy M. Chan, Zahed Rahmati

Research output: Contribution to journalArticlepeer-review


For two sequences P and Q of n points in Rd, we compute an approximation to the discrete Fréchet distance. Our f-approximation algorithm runs in time O(nlog⁡n+n2/f2), for any f∈[1,n/log⁡n] and d=O(1), which improves (and, at the same time, slightly simplifies) the previous O(nlog⁡n+n2/f)-time algorithm by Bringmann and Mulzer [SoCG’15].

Original languageEnglish (US)
Pages (from-to)72-74
Number of pages3
JournalInformation Processing Letters
StatePublished - Oct 2018


  • Approximation algorithm
  • Discrete Fréchet distance
  • Strongly subquadratic time

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'An improved approximation algorithm for the discrete Fréchet distance'. Together they form a unique fingerprint.

Cite this