Streaming Algorithms for Line Simplification

by

Mohammad Ali Abam, Mark de Berg, Peter Hachenberger and Alireza Zarei

Summary

Given a streaming input of data points, it may be impossible to store the complete set. A compromise would be to create an simplification or approximation ot those points. The simplification problem is give a path P with points p0, p1,..pn to find a path Q with fewer vertices. If Q is a subset of P it is a restricted version, in an unrestricted version this does not have to be so. There are two type of optimization problems min-k and min-delta. Min-k is given a maximum error find a simplification with as few vertices as possible that is below the error threshold. With min-delta, given a maximum of K vertices find the simplification with the smallest possible error that uses at most K vertices. Iterative algorithms are needed due to the streaming nature, and thus many existing line simplification algorithms cannot be used for streaming.

The error function between the simplified version and the original is calculated using Hausdorff and Frechet distances. The goal is to get competitive ratio in comparison between the optimal offline algorithm and the simplification algorithm.

The algorithm uses a priority queue to hold the vertex links. We compute the error of the incoming link, and insert it into the queue at the appropriate priority. Then we extract the vertex from the from the queue with the minimum priority and update the priorities of the vertices on both sides. The paper goes on to define c-montone as the error of a link cannot be worse that c times the error of any link that encloses it.

The paper goes on to discuss the Hausdorff error function, and discuss how the oracle makes use of that function. The same treatment if given to Freceht, who uses two parameters: width of the points and length of the largest back path. Each distance function is successful at differing type of point distributions.

Discussion

I had no trouble understanding the basic algorithm structure. I was a bit confused by the use of the oracles and the two distance function, but with a closer look and more examples I feel it should be come clear. I wonder how much of streaming simplification/beautification we will actually do. I cannot perceive us wanting to beautify the stroke as the user goes. If we can do such a simplification in the background it would give a head start when it comes time to process the stroke, and reduce the delay significantly. Can this be applied to arcs at all (I know they put it for a polygonal path), could the basic algorithm (not the distance functions) work?

Citation

Abam, M. A., de Berg, M., Hachenberger, P., and Zarei, A. 2007. Streaming algorithms for line simplification. In Proceedings of the Twenty-Third Annual Symposium on Computational Geometry (Gyeongju, South Korea, June 06 - 08, 2007). SCG '07. ACM Press, New York, NY, 175-183. DOI= http://doi.acm.org/10.1145/1247069.1247103