Curve Simplification and Clustering under Fréchet Distance

We present new approximation results on curve simplification and clustering under Fréchet distance. Let T = τ i : i ∈ [n] be polygonal curves in R d of m vertices each. Let ℓ be any integer from [m]. We study a generalized curve simplification problem: given error bounds δ i > 0 for i ∈ [n], find a curve σ of at most ℓ vertices such that d F (σ, τ i ) ≤ δ i for i ∈ [n]. We present an algorithm that returns a null output or a curve σ of at most ℓ vertices such that d F (σ, τ i ) ≤ δ i + εδ max for i ∈ [n], where δ max = max i∈[n] δ i . If the output is null, there is no curve of at most ℓ vertices within a Fréchet distance of δ i from τ i for i ∈ [n]. The running time is Õ n O(ℓ) • m O(ℓ 2 ) • (dℓ/ε) O(dℓ) . This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve τ to another curve σ, where the vertices of σ can be anywhere in R d , so that d F (σ, τ ) ≤ (1+ε)δ and |σ| ≤ (1+α)•min|c| : d F (c, τ ) ≤ δ for any given δ > 0 and any fixed α, ε ∈ (0, 1). The running time is Õ m O(1/α) •(d/(αε)) O(d/α) . By combining our technique with some previous results in the literature, we obtain an approximation algorithm for (k, ℓ)-median clustering. Given T , it computes a set Σ of k curves, each of ℓ vertices, such that i∈[n] min σ∈Σ d F (σ, τ i ) is within a factor 1+ε of the optimum with probability at least 1-µ for any given µ, ε ∈ (0, 1). The running time is Õ n • m O(kℓ 2 ) • µ -O(kℓ) • (dkℓ/ε) O((dkℓ/ε) log(1/µ)) .