Abstract While there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present streaming algorithms for two such problems under the Fréchet distance dF d F in Rᵈ R d for some constant d 2 d ≥ 2. Consider a polygonal curve τ in Rᵈ R d in a stream. We present a streaming algorithm that, for any (0, 1) ε ∈ (0, 1) and > 0 δ > 0, maintains a curve σ such that dF (, v₁, vᵢ) (1+) d F (σ, τ v 1, v i) ≤ (1 + ε) δ and | | 2\, opt-2 | σ | ≤ 2 opt - 2, where v₁, vᵢ τ v 1, v i is the prefix in the stream so far, and opt = \| '|: dF (', v₁, vᵢ) \ opt = min { | σ ′ |:
Cheng et al. (Sat,) studied this question.