Streaming Algorithms for Line Simplification |
| |
Authors: | M A Abam M de Berg P Hachenberger A Zarei |
| |
Institution: | 1. MADALGO, Department of Computing Science, Aarhus University, Aarhus, Denmark 2. Department of Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands 3. Computer Engineering Department, Sharif University of Technology and IPM School of Computer Science, P.O. Box 11365-9517, Tehran, Iran
|
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|