{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T09:41:41Z","timestamp":1773567701325,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00454-008-9132-4","type":"journal-article","created":{"date-parts":[[2009,1,12]],"date-time":"2009-01-12T20:09:40Z","timestamp":1231790980000},"page":"497-515","source":"Crossref","is-referenced-by-count":24,"title":["Streaming Algorithms for Line Simplification"],"prefix":"10.1007","volume":"43","author":[{"given":"M. A.","family":"Abam","sequence":"first","affiliation":[]},{"given":"M.","family":"de Berg","sequence":"additional","affiliation":[]},{"given":"P.","family":"Hachenberger","sequence":"additional","affiliation":[]},{"given":"A.","family":"Zarei","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,13]]},"reference":[{"issue":"2","key":"9132_CR1","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/PL00009500","volume":"23","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Varadarajan, K.R.: Efficient algorithms for approximating polygonal chains. Discrete Comput. Geom. 23(2), 273\u2013291 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9132_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Yu, H.: A space-optimal data-stream algorithm for coresets in the plane. In: Proceedings of ACM Symposium on Computational Geometry (SOCG), pp. 1\u201310 (2007)","DOI":"10.1145\/1247069.1247071"},{"key":"9132_CR3","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00453-005-1165-y","volume":"42","author":"P.K. Agarwal","year":"2005","unstructured":"Agarwal, P.K., Har-Peled, S., Mustafa, N.H., Wang, Y.: Near-linear time approximation algorithms for curve simplification. Algorithmica 42, 203\u2013219 (2005)","journal-title":"Algorithmica"},{"key":"9132_CR4","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1142\/S0218195995000064","volume":"5","author":"H. Alt","year":"1995","unstructured":"Alt, H., Godau, M.: Computing the Fr\u00e9chet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5, 75\u201391 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9132_CR5","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proceedings of Annual Symposium on Foundations of Computer Science (FOCS), pp. 617\u2013626 (2002)","DOI":"10.1109\/SFCS.2002.1181985"},{"key":"9132_CR6","doi-asserted-by":"crossref","unstructured":"Buragohain, C., Gandhi, S., Hershberger, J., Sur, S.: Contour approximation in sensor networks. In: Proceedings of Distributed Computing in Sensor Systems (DCOSS), pp. 356\u2013371 (2006)","DOI":"10.1007\/11776178_22"},{"key":"9132_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/3-540-56279-6_90","volume-title":"Proceedings of Annual International Symposium on Algorithms and Computing (ISAAC)","author":"W.S. Chan","year":"1992","unstructured":"Chan, W.S., Chin, F.: Approximation of polygonal curves with minimum number of line segments. In: Proceedings of Annual International Symposium on Algorithms and Computing (ISAAC). Lecture Notes in Computer Science, vol. 650, pp. 378\u2013387. Springer, Berlin (1992)"},{"key":"9132_CR8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","volume":"10","author":"D.H. Douglas","year":"1973","unstructured":"Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Can. Cartograph. 10, 112\u2013122 (1973)","journal-title":"Can. Cartograph."},{"key":"9132_CR9","doi-asserted-by":"crossref","unstructured":"Godau, M.: A natural metric for curves: Computing the distance for polygonal chains and approximation algorithms. In: Proceedings of Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 127\u2013136 (1991)","DOI":"10.1007\/BFb0020793"},{"key":"9132_CR10","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/BF02570717","volume":"14","author":"M.T. Goodrich","year":"1995","unstructured":"Goodrich, M.T.: Efficient piecewise-linear function approximation using the uniform metric. Discrete Comput. Geom. 14, 445\u2013462 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9132_CR11","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1142\/S0218195993000257","volume":"3","author":"L.J. Guibas","year":"1993","unstructured":"Guibas, L.J., Hershberger, J.E., Mitchell, J.S.B., Snoeyink, J.S.: Approximating polygons and subdivisions with minimum link paths. Int. J. Comput. Geom. Appl. 3, 383\u2013415 (1993)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9132_CR12","first-page":"132","volume":"53","author":"S.L. Hakimi","year":"1991","unstructured":"Hakimi, S.L., Schmeichel, E.F.: Fitting polygonal functions to a set of points in the plane. CVGIP: Graph. Models Image Process. 53, 132\u2013136 (1991)","journal-title":"CVGIP: Graph. Models Image Process."},{"key":"9132_CR13","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Snoeyink, J.: An O(nlog\u2009n) implementation of the Douglas\u2013Peucker algorithm for line simplification. In: Proceedings of ACM Symposium on Computational Geometry (SOCG), pp. 383\u2013384 (1994)","DOI":"10.1145\/177424.178097"},{"key":"9132_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/3-540-63307-3_50","volume-title":"Proceedings of International Workshop on Algorithms and Data Structures (WADS)","author":"J. Hershberger","year":"1997","unstructured":"Hershberger, J., Snoeyink, J.: Cartographic line simplification and polygon CSG formulae in O(nlog\u2009* n) time. In: Proceedings of International Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 1272, pp. 93\u2013103. Springer, Berlin (1997)"},{"issue":"3","key":"9132_CR15","first-page":"159","volume":"9","author":"H. Imai","year":"1986","unstructured":"Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function. J. Inf. Process. 9(3), 159\u2013162 (1986)","journal-title":"J. Inf. Process."},{"key":"9132_CR16","first-page":"71","volume-title":"Computational Morphology","author":"H. Imai","year":"1988","unstructured":"Imai, H., Iri, M.: Polygonal approximations of a curve-formulations and algorithms. In: Toussaint, G.T. (ed.) Computational Morphology, pp. 71\u201386. North-Holland, Amsterdam (1988)"},{"key":"9132_CR17","first-page":"87","volume-title":"Computational Morphology","author":"A. Melkman","year":"1988","unstructured":"Melkman, A., O\u2019Rourke, J.: On polygonal chain approximation. In: Toussaint, G.T. (ed.) Computational Morphology, pp. 87\u201395. North-Holland, Amsterdam (1988)"},{"key":"9132_CR18","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.M.: Data Streams: Algorithms and Applications. Now Publishers (2005)","DOI":"10.1561\/0400000002"},{"key":"9132_CR19","unstructured":"Zarrabi-Zadeh, H., Chan, T.: A simple streaming algorithm for minimum enclosing balls. In: Proceedings of Canadian Conference on Computational Geometry (CCCG), pp. 139\u2013142 (2006)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9132-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T22:44:36Z","timestamp":1738881876000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-008-9132-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,13]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9132"],"URL":"https:\/\/doi.org\/10.1007\/s00454-008-9132-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,13]]}}}