Simplification of Trajectory Streams

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 $$d_F$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:math> in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> for some constant $$d \ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . Consider a polygonal curve $$\tau $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>τ</mml:mi> </mml:math> in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> in a stream. We present a streaming algorithm that, for any $$\varepsilon \in (0,1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$\delta &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , maintains a curve $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> such that $$d_F(\sigma ,\tau [v_1,v_i])\le (1+\varepsilon )\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>σ</mml:mi> <mml:mo>,</mml:mo> <mml:mi>τ</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>v</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>δ</mml:mi> </mml:mrow> </mml:math> and $$|\sigma |\le 2\,\textrm{opt}-2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>σ</mml:mi> <mml:mo>|</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> <mml:mspace/> <mml:mtext>opt</mml:mtext> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , where $$\tau [v_1,v_i]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>τ</mml:mi> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>v</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> is the prefix in the stream so far, and $$\textrm{opt} = \min \{|\sigma '|: d_F(\sigma ',\tau [v_1,v_i])\le \delta \}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>opt</mml:mtext> <mml:mo>=</mml:mo> <mml:mo>min</mml:mo> <mml:mo>{</mml:mo> <mml:mo>|</mml:mo> <mml:msup> <mml:mi>σ</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>|</mml:mo> <mml:mo>:</mml:mo> <mml:msub>