2014/01/01 by Pankaj Agarwal, Pankaj K. Agarwal, Rinat Ben Avraham +2 · 7 citations
Computer Science · #Algorithms and Data Compression #semigroups and automata theory #Cellular Automata and Applications
paper · doi:10.1137/130920526
The Fréchet distance measures similarity between two curves f and g that takes into account the ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along f, and its owner, walking along g, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on m and n specific stones, respectively. The stones are in fact sequences of points, typically sampled from the respective curves f and g. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops from the starting points to the terminal points of their sequences. The discrete Fréchet distance can be computed in O(mn) time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m≤ n, the algorithm runs in O((mnloglog n)/(log n)) time, in the word RAM model, using O(n) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.