Streaming algorithms for line simplification under the Fréchet distance

We study the following variant of the well-known linesimplification problem: we are getting a possibly infinite sequence of points p0, p1, p2, . . . defining a polygonal path, and as we receive the points we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage so that we cannot store all the points. We analyze the competitive ratio of our algorithm, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points, and compare the error of our simplification to the error of the optimal simplification with k points.