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

1 Introduction

• The discrete Fréchet distance measures the smallest maximum separation in a joint sequence of forward hops between sampled curves, and the standard dynamic program takes O(n^2) time.It approximates the continuous distance when samples are dense enough; strongly subquadratic algorithms are unlikely even for approximation within a factor of 3 [BOS19].Source: §1 · p. 2
• The paper initiates a formal study of parallel Fréchet computation, focusing on PRAM and MPC after earlier work left parallel algorithms largely unexplored.The authors frame the results as a theoretical foundation for parallel-efficient Fréchet algorithms, motivated in part by massively parallel trajectory analysis.Source: §1 · p. 3

1.1 Results and technical ideas

• The exact decision algorithm combines reachability information for adjacent matrix strips over O(log n) iterations, then uses multi-pivot search over pairwise distances to find the DFD.The decision problem asks whether an n × n binary matrix has a rightward-and-upward path of 1-entries from M[1,1] to M[n,n].Source: §1.1 · pp. 3–4
• O(log n/σ) PRAM rounds and O~(n^(2+σ)) total work, or O(log n/ρ^2) MPC rounds and O(n^(2+ρ)) total space, compute the exact DFD.The PRAM bound holds for any σ > 0; the MPC bound holds for constant ρ ∈ (0, 1).Source: §1.1 · p. 4
• O(1/ρ) MPC rounds with O~(n) total space and work compute a (2/ρ + 1)-relaxed μ-simplification; PRAM computes an O(log n)-relaxed simplification in O(log n) rounds.The PRAM algorithm uses O(n) processors and O(n log n) total work. The simplifications enable an implicit dynamic-programming matrix with at most O(c) 1-entries per row and column; tiling then identifies relevant submatrices.Source: §1.1 · p. 4
• O(log n + 1/σ^3) PRAM rounds and O(n^(1+σ)) total work, and O(1/ρ^3) MPC rounds and O(n^(1+ρ)) total space, suffice for a (1 + ε)-approximation on c-packed curves.The PRAM result applies for Θ(log c / log n) ≤ σ < 1; the MPC result applies for constant ρ ∈ (0, 1).Source: §1.1 · p. 5

2 Preliminaries

• A walk starts at (1, 1), ends at (n, n), and advances one or both indices by one; the discrete Fréchet distance minimizes the maximum paired-vertex distance along such a walk.The curves are assumed to have n vertices for simplicity, an assumption the paper says can be removed.Source: §2 · p. 5
• The distance computation is equivalent to finding a minimum-bottleneck monotone path in the n × n distance matrix and takes O(n^2) time by dynamic programming.For a threshold δ, deciding whether the distance is at most δ is grid reachability using only cells whose paired-vertex distance is at most δ.Source: §2 · p. 5

Models of computation

• PRAM algorithms are analyzed by DAG height (rounds), maximum layer width (processors), and total operation nodes (work), with the paper using common CRCW PRAM.The model has synchronous shared-memory processors and permits concurrent reads and writes only when writers attempt the same value.Source: Models of computation · p. 6
• MPC is a synchronous distributed model with per-machine space S, at most S words sent or received per round, and total space M · S, assumed at least the input size N.Machines perform local computation after receiving messages; round complexity is the worst-case number of rounds until termination.Source: Models of computation · p. 6

3 “Trivial” algorithms in the PRAM model

• 2n −1 rounds and O(n^2) total work suffice to compute the DFD of two length-n curves.In each round, processors compute reachability values for cells on one matrix diagonal.Source: §3 · p. 7
• O(log n) rounds and O(n^6 log n) total work suffice to compute the DFD of two length-n curves using directed reachability.The algorithm applies a transitive-closure procedure to the directed graph corresponding to Mδ, which has O(n^2) vertices.Source: §3 · p. 8
• O(1) rounds and 2^O(n) total work suffice to compute the DFD of two length-n curves by checking all possible directed paths in parallel.Each path can be verified in one round by checking whether all its cells are 1-entries.Source: §3 · p. 8

• Boundary reachability information lets the algorithm merge strips without retaining each strip’s full Θ(n^2)-size matrix.The method stores only a constant number of values per boundary cell.Source: §4 · p. 8
• O(1) PRAM rounds and Õ(n) total work suffice to merge the reachability information of two strips that share one column.The resulting information describes the combined strip.Source: §4 · p. 9
• O(log n) rounds and Õ(n^2) total work suffice in the PRAM model to decide whether the discrete Fréchet distance exceeds a threshold δ.The algorithm applies to two curves of length n.Source: §4 · p. 10
• The PRAM decision algorithm implies an MPC algorithm with O(n^ρ) space per machine, O(log n/ρ) rounds, and Õ(n^2) total space.Source: §4 · p. 10

5 Simplifying a curve in parallel

• Parallel simplification targets a useful approximation heuristic: replace a curve with a simpler curve that stays relatively close under discrete Fréchet distance.The section says these simplifications will be used in the next section to approximate the distance between realistic curves.Source: §5 · p. 10
• The sequential µ-simplification from selects the first later vertex more than µ from the current vertex, producing subcurves within µ and simplified edges longer than µ.The process starts at the first vertex and continues until the last vertex.Source: §5 · p. 10
• Because this procedure is inherently sequential, parallel merging requires relaxing the condition that every point in a subcurve lies within µ of its representative vertex.The section introduces α-relaxed µ-simplifications for α > 1, with the curve partitioned into disjoint subcurves containing the corresponding simplified vertices.Source: §5 · p. 10

5.1 Simplification in the MPC model

• The MPC subsection specifies that the simplified curve’s edges have length greater than µ.This is the long-edges condition stated for the α-relaxed µ-simplification.Source: §5.1 · p. 10, §5 · p. 10

Warmup: Simplification with ˜O(√n) space per machine and O(1) rounds

• The two-round method locally simplifies each subcurve, compresses consecutive singleton runs, then merges across neighboring elements to remove short edges.The second-round merge deletes vertices when neighboring distances are at most µ; the resulting simplification retains the 5-relaxed µ guarantee.Source: Warmup: Simplification with ˜O(√n)… · p. 11
• In two MPC rounds with ˜O(√n) space per machine, the algorithm computes a 5-relaxed µ-simplification of P.It assumes P is divided into √n consecutive subcurves of √n vertices each, an arrangement obtainable in O(1) rounds.Source: Warmup: Simplification with ˜O(√n)… · pp. 10–11
• For any ρ < 1, MPC computes a (2/ρ + 1)-relaxed µ-simplification in O(1/ρ) rounds with O(n^ρ) space per machine; PRAM achieves an O(log n)-relaxed µ-simplification in O(log n) rounds.The MPC algorithm uses ˜O(n) total space and total work; the PRAM algorithm uses O(n) processors and O(n log n) total work.Source: Warmup: Simplification with ˜O(√n)… · p. 12

6 Realistic curves

• If every row and column of an n × n binary matrix has at most λ 1-entries, at most 4λk submatrices in the k-by-k partition are relevant.A submatrix is relevant when a boundary cell contains a 1-entry.Source: §6 · p. 13

6.1 Finding the relevant submatrices

• When each matrix row and column has at most λ 1-entries, relevant submatrices can be found in O(1/ρ) MPC rounds using O(λn^ρ) space per machine and O(λn^1+ρ) total space.The output contains at most 4λn^1−ρ submatrices; the PRAM version uses O(λn^1+ρ) processors in O(1/ρ) rounds.Source: §6.1 · p. 14

6.2 The decision problem

• The approximate decision algorithm takes O(1/ρ^2) MPC rounds with O(n^ρ) per-machine and O(n^1+ρ) total space, or O(log n + 1/σ^2) PRAM rounds with O(n^1+σ) work.For constant ε and the stated parameter conditions, it returns a correct (1 + ε)-approximation or correctly determines whether the distance is below or above δ.Source: §6.2 · p. 16

6.3 Optimization

• For c-packed curves, a (1 + ε)-approximation takes O(log n + 1/σ^3) PRAM rounds and O(n^1+σ) work, or O(1/ρ^3) MPC rounds and O(n^1+ρ) space.The PRAM bound holds for Θ(log c/log n) ≤ σ < 1; the MPC bound holds for constant ρ ∈ (0, 1).Source: §6.3 · p. 16

Conclusion

• The paper presents the first parallel algorithms for the discrete Fréchet distance in PRAM and MPC, plus more efficient algorithms for c-packed curves.The c-packed algorithms also require a parallel simplification algorithm, which may be of independent interest; the algorithms are close to optimal in total work given the SETH-based lower bounds in.Source: Conclusion · p. 16
• A strip-based divide-and-conquer approach can adapt the discrete decision algorithms to the continuous Fréchet distance, recursively computing reachability on strip boundaries.This approach is described as slightly simpler than the similar free-space-diagram method of Alt and Godau.Source: Conclusion · pp. 16–17
• Parallel algorithms for the discrete Fréchet distance when only one curve is c-packed remain an open question.Sequential near-linear-time algorithms exist for the discrete and continuous distances and, respectively.Source: Conclusion · p. 17
• Whether general-curve discrete Fréchet distance can be computed in O(1) MPC rounds remains open.One possible direction is adapting [CZ24], which reduces dynamic programming problems to planar-graph problems with known node embeddings; its techniques do not readily extend to the directed-reachability or exact undirected-shortest-path problem corresponding to this dynamic program.Source: Conclusion · p. 17

A.1 Decision in the MPC model

• The DFD decision problem takes O(log n/ρ) MPC rounds, with Θ(n^ρ) local space per machine and ~O(n^2) total space.The theorem states ρ > 0 is any constant.Source: §A.1 · p. 19
• Given reachability information for two strips S[j1,j2] and S[j2,j3], the reachability information for S[j1,j3] can be computed in O(1/ρ) rounds and ˜O(n) total space; the algorithm then performs O(log n) iterations merging pairs of strips.Source: §A.1 · pp. 19–20

A.2 Optimization

• The exact DFD takes O(log n/σ) PRAM rounds and ~O(n^(2+σ)) work, or O(log n/ρ^2) MPC rounds and ~O(n^(2+ρ)) space.The MPC bound assumes constant ρ in (0, 1); the PRAM bound holds for any σ > 0.Source: §A.2 · p. 20
• The MPC exact search sorts all n^2 pairwise point distances, then uses n^ρ quantiles and parallel decision calls to locate the DFD value in O(1/ρ) recursion depth.The PRAM variant instead chooses n^σ random pivots per step and recurses to the interval containing the DFD, with depth O(1/σ).Source: §A.2 · p. 20

A.3 The continuous Fréchet distance

• Alt and Godau compute continuous-Fréchet reachability by recursively splitting free-space diagrams and finding reachable boundary extrema for intervals.Their method partitions the boundary into intervals and determines the lowest and highest reachable points on the opposite side.Source: §A.3 · p. 20
• For the continuous Fréchet distance, strips can replace smaller diagrams; recursively computing reachability on each strip’s left and right boundaries uses interval partitioning.The resulting PRAM and MPC algorithms are similar to those for the discrete version.Source: §A.3 · pp. 20–21

B.1 Simplification in the MPC model

• With O(n^ρ) space per MPC machine, the hierarchy has 1/ρ levels, each grouping n^ρ consecutive subcurves from the preceding level.The parameter assumes 1/ρ is an integer, reducing ρ if necessary.Source: §B.1 · p. 21
• At each MPC level, machines simplify maximal consecutive singleton runs at scale 2μ and pass at most three elements per child subcurve upward.Each machine receives O(n^ρ) elements; pairs serve as breakpoints between singleton runs.Source: §B.1 · pp. 21–22
• Before merging, every retained pair has endpoints more than 2μ apart, and each partition subcurve lies within (2/ρ)μ of its representative.The analysis uses a forest whose root spans partition the curve into ordered, disjoint consecutive subcurves.Source: §B.1 · pp. 22–23
• A (2/ρ + 1)-relaxed μ-simplification of P results after the MPC merge round.The proof establishes the required distance and long-edge properties for the resulting subsequence.Source: §B.1 · p. 23

B.2 Simplification in the PRAM model

• An O(log n)-relaxed μ-simplification of an n-vertex curve is computable in O(log n) rounds with O(n) processors in PRAM.The algorithm and analysis translate the MPC approach to PRAM.Source: §B.2 · p. 24
• In PRAM, each processor handles at most four elements per level, simplifies singleton runs, and passes at most three elements to the next level.After the last step, the algorithm propagates information back to level zero and performs the merge in O(1) rounds.Source: §B.2 · p. 24

C.1 Bounding the complexity of the matrix

• Every α-relaxed µ-simplification of a c-packed curve is 6αc-packed.The proof compares the original curve’s length inside an expanded ball with the simplification’s length, deriving contradictions for both r ≥ αµ and r < αµ.Source: §C.1 · pp. 24–25
• For a ball B of radius (1 + ε/2)δ, Claim 6’s 6αc-packedness argument bounds the number |V| of contained simplification vertices by O(α²c/ε), not matrix entries.The proof enlarges B by εδ/(4α); each contained vertex then contributes at least εδ/(4α) length inside the larger ball, whose curve length is at most 6αc(1 + ε/2 + ε/(4α))δ.Source: §C.1 · p. 25
• Each row and column of M has O(α^2c/ε) 1-entries.The bound follows by limiting the number of simplification vertices in the ball associated with a row or column.Source: §C.1 · p. 25

C.2 The decision problem in the PRAM model

• Each relevant submatrix M′ has n^σ rows and columns and O(α^2c/ε) boundary 1-entries.The PRAM algorithm first computes the simplification and identifies these submatrices.Source: §C.2 · p. 25
• Parallel reachability tests between boundary 1-entries reduce the relevant submatrices to a graph of size Õ(c n^(1−σ)/(εσ^2)).For each submatrix, the procedure records which boundary 1-entries are reachable from each other.Source: §C.2 · p. 25
• The PRAM decision procedure uses O(σ log n + 1/σ^2) rounds.It recursively reduces the graph until its size is O(n^σ), then tests reachability from M[1,1] to M[n,n].Source: §C.2 · p. 25

C.3 Optimization

• For n sorted real points, MPC constructs Õ(n) candidate distances in O(1) rounds and Õ(n) total space, with some candidate r satisfying r/2 ≤ |x − y| ≤ r for every pair.The algorithm computes distances from each point to O(log n) nearby indices selected across progressively finer partitions.Source: §C.3 · p. 26
• For points in R^d, an MPC algorithm constructs Õ(nd) candidate distances so every pairwise distance has an r with r ≤ ∥x − y∥₂ ≤ (1 + ε)r, in O(1) rounds and Õ(nd) total space.It combines coordinatewise candidate distances with geometric scaling by powers of (1 + ε).Source: §C.3 · p. 26
• For c-packed curves, MPC computes a (1+ε)-approximation in O(1/ρ^3) rounds using n^ρ space per machine and Õ(n^(1+ρ)) total space.The algorithm builds candidate distances and uses parallel multi-pivot search with recursion depth O(1/ρ).Source: §C.3 · pp. 26–27
• For c-packed curves and Θ(log c/log n) ≤ σ < 1, PRAM computes a (1+ε)-approximation in O(log n + 1/σ^3) rounds with Õ(n^(1+σ)) total work.The approach constructs a candidate distance set and then performs multi-pivot search.Source: §C.3 · p. 27