arXiv preprint ·
How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Coresets for $k$-Means: When Does Uniform Sampling Suffice?
CyberHull: Deterministic Malicious URL Isolation via Convex Hull
VisFlow: Interpretable Flow Matching for Visibility Reconstruction, Characterization, and Recognition
Splitting Planar Necklaces with Few Straight Cuts
A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.