Parallel algorithms speed up measuring similarity between polygonal curves
How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
Data Structures and AlgorithmsComputational Geometry
Summary
Measuring how similar two curved paths are can be tricky and slow, especially for long paths. The Fréchet distance measures this similarity and is sometimes called the dog-leash distance because it imagines walking a dog along one path while you walk on another. The authors developed new methods to compute this distance much faster by using many computers at once working in parallel. Their methods work efficiently for both general and special types of curves, and they also showed ways to simplify curves quickly in parallel as part of this process.
What this means in practice
- •For geospatial data engineers: Speed up similarity checks between geographic paths by efficiently computing discrete Fréchet distance in parallel on large datasets.
- •For computer graphics developers: Use parallel curve simplification methods to speed up rendering and analysis of complex polygonal shapes and animations.
Authors
Leonid Barenboim, Arnold Filtser, Omrit Filtser, Orr Fischer
Abstract
The Fréchet distance (also known as the dog-leash distance) is a well-studied and prevalent distance measure for polygonal curves. In this paper we present parallel algorithms for computing the discrete \frechet\ distance between two curves, in both the PRAM and MPC models. For two polygonal curves of length $n$, we show that the distance between them can be computed in the PRAM model in $O(\log n/ σ)$ rounds and $\tilde{O}(n^{2+σ})$ total work for any $0<σ<1$. In the sublinear MPC model with $n^ρ$ space per machine, it can be computed in $O(\log n / ρ^2)$ rounds and $\tilde{O}(n^{2+ρ})$ total space. For $c$-packed curves, we match our bounds to the sequential algorithms, showing that a $(1+\eps)$-approximation of the distance can be computed in the PRAM model in $O(\log{n}+1/σ^3)$ rounds and $\tilde{O}(n^{1+σ})$ total work, and in the sublinear MPC model in $O(1 /ρ^3)$ rounds and $\tilde{O}(n^{1+ρ})$ total space, for any constant $\eps>0$. As part of our algorithms for $c$-packed curves, we also present parallel algorithms for computing curve simplifications, which may be of independent interest.