Streaming algorithms for line simplification

M.A. Abam, M. Berg, de, P. Hachenberger, A. Zarei

Research output: Contribution to journalArticleAcademicpeer-review

25 Citations (Scopus)
2 Downloads (Pure)

Abstract

We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p 0,p 1,p 2,… in the plane 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 algorithms, 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. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k 2) additional storage. Keywords: Line simplification - Streaming algorithms.
Original languageEnglish
Pages (from-to)497-515
JournalDiscrete and Computational Geometry
Volume43
Issue number3
DOIs
Publication statusPublished - 2010

Fingerprint Dive into the research topics of 'Streaming algorithms for line simplification'. Together they form a unique fingerprint.

Cite this