Four Soviets walk the dog: improved bounds for computing the Fréchet distance

K.A. Buchin, M. Buchin, W. Meulemans, W. Mulzer

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
89 Downloads (Pure)

Abstract

Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n 2 logn) O(n2log⁡n) algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here, n denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time O(n 2 logn − − − − √ (loglogn) 3/2 ) O(n2log⁡n(log⁡log⁡n)3/2) on a pointer machine and in time O(n 2 (loglogn) 2 ) O(n2(log⁡log⁡n)2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n 2−ε ) O(n2−ε) , for some ε>0 ε>0 . We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fréchet distance on a word RAM.
Original languageEnglish
Pages (from-to)180-216
Number of pages37
JournalDiscrete and Computational Geometry
Volume58
Issue number1
Early online date27 Feb 2017
DOIs
Publication statusPublished - 1 Jul 2017

Keywords

  • Algebraic decision tree
  • Four Russian trick
  • Frechet distance
  • Pointer machine
  • Word RAM

Fingerprint Dive into the research topics of 'Four Soviets walk the dog: improved bounds for computing the Fréchet distance'. Together they form a unique fingerprint.

  • Cite this