Cyber-Physical Systems

Quality-Guaranteed Data Streaming in Resource-Constrained Cyber-Physical Systems 237

Lemma 9.2 Suppose that a line segment s approximates a fragment X of n points x

1

, ..., x

n

in a

time series. Then, s minimizes segerr(s, X) if the slope of s is

m =

(



n

i=1

ix

i

) −

1

n



n

i=1

i



n

i=1

x

i





n

i=1

i

2



−

1

n





n

i=1

i



2

(9.5)

and the left endpoint of s has value

m +



n

i=1

(x

i

−i · m)

n

Proof: Consider a line segment s approximating fragment X. Let the left endpoint of s be (1, y

1

)

and the slope be m. For each point x

i

(1 ≤ i ≤ n), the error is |x

i

−˜x

i

| = |x

i

− y

1

− m(i − 1)|.

Thus,

segerr =

n



i=1

(x

i

−y

1

−m(i − 1))

2

(9.6)

Clearly, when y

1

= m +



n

i=1

(x

i

−i·m)

n

, segerr reaches the minimum value ...