{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:36Z","timestamp":1725663396606},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540549451"},{"type":"electronic","value":"9783540466000"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54945-5_59","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T23:18:39Z","timestamp":1330211919000},"page":"151-162","source":"Crossref","is-referenced-by-count":8,"title":["Approximating polygons and subdivisions with minimum link paths"],"prefix":"10.1007","author":[{"given":"Leonidas J.","family":"Guibas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John E.","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack Scott","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0097-3165(89)90032-0","volume":"52","author":"P. K. Agarwal","year":"1989","unstructured":"P. K. Agarwal, M. Sharir, and P. Shor. Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences. J. Comb. Theory A, 52:228\u2013274, 1989.","journal-title":"J. Comb. Theory A"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"H. Alt, J. Bl\u00f6mer, M. Godau, and H. Wagener. Approximation of convex polygons. In Seventeenth ICALP, number 443 in LNCS, pages 703\u2013716. Springer-Verlag, 1990.","DOI":"10.1007\/BFb0032068"},{"key":"18_CR3","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1145\/366573.366611","volume":"4","author":"R. Bellman","year":"1961","unstructured":"R. Bellman. On the approximation of curves by line segments using dynamic programming. CACM, 4:284, 1961.","journal-title":"CACM"},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.3138\/1005-13MG-2627-2552","volume":"21","author":"M. Blakemore","year":"1984","unstructured":"M. Blakemore. Generalisation and error in spatial data bases. Cartographica, 21:131\u2013139, 1984.","journal-title":"Cartographica"},{"key":"18_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3138\/FWV8-3802-2282-6U47","volume":"22","author":"B. Buttenfield","year":"1985","unstructured":"B. Buttenfield. Treatment of the cartographic line. Cartographica, 22:1\u201326, 1985.","journal-title":"Cartographica"},{"issue":"2","key":"18_CR6","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"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"P. Egyed and R. Wenger. Ordered stabbing of pairwise disjoint convex sets in linear time. Disc. App. Math., to appear.","DOI":"10.1016\/0166-218X(91)90065-5"},{"key":"18_CR8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Comp. Sci., 1:237\u2013267, 1976.","journal-title":"Theoretical Comp. Sci."},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"S. K. Ghosh","year":"1991","unstructured":"S. K. Ghosh. Computing the visibility polygon from a convex set and related problems. J. Alg., 12:75\u201395, 1991.","journal-title":"J. Alg."},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. Graham","year":"1972","unstructured":"R. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Info. Proc. Let., 1:132\u2013133, 1972.","journal-title":"Info. Proc. Let."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry. In Proc. 24th FOCS, pages 100\u2013211, 1983.","DOI":"10.1109\/SFCS.1983.1"},{"issue":"2","key":"18_CR12","first-page":"132","volume":"53","author":"S. L. Hakimi","year":"1991","unstructured":"S. L. Hakimi and E. F. Schmeichel. Fitting polygonal functions to a set of points in the plane. CVGIP: Graph. Mod. Image Proc., 53(2):132\u2013136, 1991.","journal-title":"CVGIP: Graph. Mod. Image Proc."},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. In WADS '91 Proceedings, 1991.","DOI":"10.1007\/BFb0028273"},{"key":"18_CR14","unstructured":"J. Hershberger and J. Snoeyink. An implementation of the Douglas-Peucker line simplification algorithm using at most cn log n operations. In preparation, 1991."},{"key":"18_CR15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0734-189X(86)80027-5","volume":"36","author":"H. Imai","year":"1986","unstructured":"H. Imai and M. Iri. Computational-geometric methods for polygonal approximations of a curve. Comp. Vis. Graph. Image Proc., 36:31\u201341, 1986.","journal-title":"Comp. Vis. Graph. Image Proc."},{"issue":"3","key":"18_CR16","first-page":"159","volume":"9","author":"H. Imai","year":"1986","unstructured":"H. Imai and M. Iri. An optimal algorithm for approximating a piecewise linear function. J. Info. Proc., 9(3):159\u2013162, 1986.","journal-title":"J. Info. Proc."},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"H. Imai and M. Iri. Polygonal approximations of a curve\u2014formulations and algorithms. In G. T. Toussaint, editor, Computational Morphology. North Holland, 1988.","DOI":"10.1016\/B978-0-444-70467-2.50011-4"},{"key":"18_CR18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Disc. & Comp. Geom., 1:59\u201371, 1986.","journal-title":"Disc. & Comp. Geom."},{"key":"18_CR19","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, Amer. Cartog., 13:103\u2013116, 1986.","journal-title":"Amer. Cartog."},{"issue":"2","key":"18_CR20","doi-asserted-by":"crossref","first-page":"74","DOI":"10.3138\/3535-7609-781G-4L20","volume":"24","author":"R. B. McMaster","year":"1987","unstructured":"R. B. McMaster. Automated line generalization. Cartographica, 24(2):74\u2013111, 1987.","journal-title":"Cartographica"},{"issue":"1","key":"18_CR21","doi-asserted-by":"crossref","first-page":"101","DOI":"10.3138\/C213-3627-90X7-LR15","volume":"26","author":"R. B. McMaster","year":"1989","unstructured":"R. B. McMaster. The integration of simplification and smoothing algorithms in line generalization. Cartographica, 26(1):101\u2013121, 1989.","journal-title":"Cartographica"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"A. Melkman and J. O'Rourke. On polygonal chain approximation. In G. T. Toussaint, editor, Computational Morphology. North Holland, 1988.","DOI":"10.1016\/B978-0-444-70467-2.50012-6"},{"key":"18_CR23","volume-title":"Topology: A First Course","author":"J. R. Munkres","year":"1975","unstructured":"J. R. Munkres. Topology: A First Course. Prentice-Hall, Englewood Cliffs, N.J., 1975."},{"issue":"9","key":"18_CR24","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1145\/358746.358758","volume":"24","author":"J. O'Rourke","year":"1981","unstructured":"J. O'Rourke. An on-line algorithm for fitting straight lines between data ranges. CACM, 24(9):574\u2013578, Sept. 1981.","journal-title":"CACM"},{"key":"18_CR25","volume-title":"Discussion Paper 10, Michigan Inter-University Community of Mathematical Geographers","author":"J. Perkal","year":"1966","unstructured":"J. Perkal. On the length of empirical curves. In Discussion Paper 10, Michigan Inter-University Community of Mathematical Geographers, University of Michigan, Ann Arbor, 1966."},{"key":"18_CR26","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. Comp. Vis. Graph. Image Proc., 1:244\u2013256, 1972.","journal-title":"Comp. Vis. Graph. Image Proc."},{"key":"18_CR27","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0734-189X(86)90113-1","volume":"33","author":"A. Rosenfeld","year":"1986","unstructured":"A. Rosenfeld. Axial representation of shape. Comp. Vis. Graph. Image Proc., 33:156\u2013173, 1986.","journal-title":"Comp. Vis. Graph. Image Proc."},{"key":"18_CR28","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S. Suri","year":"1986","unstructured":"S. Suri. A linear time algorithm for minimum link paths inside a simple polygon. Comp. Vis. Graph. Image Proc., 35:99\u2013110, 1986.","journal-title":"Comp. Vis. Graph. Image Proc."},{"key":"18_CR29","unstructured":"G. Toussaint. On the complexity of approximating polygonal curves in the plane. In Proc. IASTED, International Symposium on Robotics and Automation, Lugano, Switzerland, 1985."}],"container-title":["Lecture Notes in Computer Science","ISA'91 Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54945-5_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:55Z","timestamp":1605646615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54945-5_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540549451","9783540466000"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-54945-5_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}