📖
How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
Leonid Barenboim, Arnold Filtser, Omrit Filtser, Orr Fischer

How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
Author / Organization Leonid Barenboim, Arnold Filtser, Omrit Filtser, Orr Fischer
Subject & Discipline cs.DS
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-268075
Original Source Link Visit Source Page on arxiv.org »