{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T21:06:37Z","timestamp":1761512797650},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_50","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T15:22:48Z","timestamp":1270480968000},"page":"93-103","source":"Crossref","is-referenced-by-count":5,"title":["Cartographic line simplication and polygon CSG formulae in O(n log* n) time"],"prefix":"10.1007","author":[{"given":"John","family":"Hershberger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01908629","volume":"10","author":"D. Dobkin","year":"1993","unstructured":"D. Dobkin, L. Guibas, J. Hershberger, and J. Snoeyink. An efficient algorithm for finding the CSG representation of a simple polygon. Algorithmica, 10:1\u201323, 1993.","journal-title":"Algorithmica"},{"issue":"2","key":"8_CR2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","volume":"10","author":"D. H. Douglas","year":"1973","unstructured":"D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a line or its caricature. The Canadian Cartographer, 10(2):112\u2013122, 1973.","journal-title":"The Canadian Cartographer"},{"issue":"1","key":"8_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0218195991000025","volume":"1","author":"L. Guibas","year":"1991","unstructured":"L. Guibas, J. Hershberger, and J. Snoeyink. Compact interval trees: A data structure for convex hulls. International Journal of Computational Geometry & Applications, 1(1):1\u201322, 1991.","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. J. Guibas","year":"1987","unstructured":"L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209\u2013233, 1987.","journal-title":"Algorithmica"},{"key":"8_CR5","unstructured":"J. Hershberger and J. Snoeyink. Speeding up the Douglas-Peucker line simplification algorithm. In Proceedings of the 5th International Symposium on Spatial Data Handling, pages 134\u2013143. IGU Commission on GIS, 1992."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"J. Hershberger and J. Snoeyink. An O(n log n) implementation of the Douglas-Peucker line simplification algorithm. In Proceedings of the Tenth Annual ACM Symposium on Computational Geometry, pages 383\u2013384, 1994. Video Review of Computational Geometry. 4:45 animation.","DOI":"10.1145\/177424.178097"},{"key":"8_CR7","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"68","author":"K. Hoffmann","year":"1986","unstructured":"K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan. Sorting Jordan sequences in linear time. Information and Control, 68:170\u2013184, 1986.","journal-title":"Information and Control"},{"key":"8_CR8","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1559\/152304086783900059","volume":"13","author":"R. B. McMaster","year":"1986","unstructured":"R. B. McMaster. A statistical analysis of mathematical measures for linear simplification. The American Cartographer, 13:103\u2013116, 1986.","journal-title":"The American Cartographer"},{"key":"8_CR9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","volume":"25","author":"A. A. Melkman","year":"1987","unstructured":"A. A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters, 25:11\u201312, 1987.","journal-title":"Information Processing Letters"},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166\u2013204, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR11","unstructured":"D. P. Peterson. Halfspace representation of extrusions, solids of revolution, and pyramids. SANDIA Report SAND84-0572, Sandia National Laboratories, 1984."},{"key":"8_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry\u2014An Introduction. Springer-Verlag, New York, 1985."},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/S0146-664X(72)80017-0","volume":"1","author":"U. Ramer","year":"1972","unstructured":"U. Ramer. An iterative procedure for the polygonal approximation of plane curves. Computer Vision, Graphics, and Image Processing, 1:244\u2013256, 1972.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"8_CR14","unstructured":"G. Rote. Quadratic convergence of the sandwich algorithm for approximating convex functions and convex figures in the plane. In Proceedings of the Second Canadian Conference on Computational Geometry, pages 120\u2013124, Ottawa, Ontario, 1990."},{"issue":"1","key":"8_CR15","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1559\/152304085783914703","volume":"12","author":"E. R. White","year":"1985","unstructured":"E. R. White. Assessment of line-generalization algorithms using characteristic points. The American Cartographer, 12(1):17\u201327, 1985.","journal-title":"The American Cartographer"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,8]],"date-time":"2018-10-08T18:14:30Z","timestamp":1539022470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}