“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 10846 |
|
||||||||
| Abstract: | |||||||||
|
We study the following variant of the well-known line-simpli-ficationproblem: we are getting a possibly infinite sequence of points p0,p1,p2,... in the plane defining a polygonal path, and as wereceive the points we wish to maintain a simplification of the pathseen so far. We study this problem in a streaming setting, where weonly have a limited amount of storage so that we cannot store all thepoints. We analyze the competitive ratio of our algorithms, allowingresource augmentation: we let our algorithm maintain a simplificationwith 2k (internal) points, and compare the error of oursimplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio forthree cases: convex paths where the error is measured using theHausdorff distance (or Frechet distance), xy-monotone paths where the error is measured using theHausdorff distance (or Frechet distance), and general paths where the error is measured using theFrechet distance. In the first case the algorithm needs O(k) additionalstorage, and in the latter two cases the algorithm needs O(k2) additional storage.
Download TeX format |
|||||||||
| back to top | |||||||||
