Streaming Algorithms for Line Simplification
Streaming Algorithms for Line Simplification
复制标题
用于简化线路的流式算法
DOI：
10.1145/1247069.1247103
复制
发表时间：
2007
影响因子：
0.8
通讯作者：
Alireza Zarei
中科院分区：
文献类型：
--
作者：
Mohammad Ali Abam;M. D. Berg;Peter Hachenberger;Alireza Zarei
我们研究著名的线简化问题的以下变体：我们在定义多边形路径的平面中得到一个（可能是无限的）点序列p0，p1，p2，...，当我们接收到这些点时，我们希望保持迄今为止所看到的路径的简化。我们在流设置中研究这个问题，其中我们只有有限的存储量，因此我们不能存储所有的点。我们分析了我们的算法的竞争比，允许资源增加：我们让我们的算法保持一个2k（内部）点的简化，并将我们的简化的错误与k点的最佳简化的错误进行比较。我们得到了三种情况下具有O（1）竞争比的算法：凸路径，其中误差使用Hausdorff距离（或Fréchet距离）测量，xy-单调路径，其中误差使用Hausdorff距离（或Fréchet距离）测量，以及一般路径，其中误差使用Fréchet距离测量。在第一种情况下，算法需要O（k）额外的存储空间，在后两种情况下，算法需要O（k2）额外的存储空间。
We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p0,p1,p2,… 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(k2) additional storage.