{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T16:26:19Z","timestamp":1790612779538,"version":"4.1.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,7,1]],"date-time":"1993-07-01T00:00:00Z","timestamp":741484800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,7]]},"DOI":"10.1007\/bf01908629","type":"journal-article","created":{"date-parts":[[2005,7,22]],"date-time":"2005-07-22T15:56:24Z","timestamp":1122047784000},"page":"1-23","source":"Crossref","is-referenced-by-count":25,"title":["An efficient algorithm for finding the CSG representation of a simple polygon"],"prefix":"10.1007","volume":"10","author":[{"given":"David","family":"Dobkin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonidas","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01908629_CR1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/MCG.1982.1674155","volume":"2","author":"J. Boyse","year":"1982","unstructured":"J. Boyse and J. Gilchrist. GMSolid: Interactive modeling for design and analysis of solids.IEEE Comput. Graphics and Applications, 2:86\u201397, 1982.","journal-title":"IEEE Comput. Graphics and Applications"},{"key":"BF01908629_CR2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/MCG.1982.1674167","volume":"2","author":"C. Brown","year":"1982","unstructured":"C. Brown. PADL-2: A technical summary.IEEE Comput. Graphics and Applications, 2:69\u201384, 1982.","journal-title":"IEEE Comput. Graphics and Applications"},{"key":"BF01908629_CR3","volume-title":"ACM Distinguished Dissertations","author":"M. H. Brown","year":"1988","unstructured":"M. H. Brown.Algorithm Animation. ACM Distinguished Dissertations. MIT Press, Cambridge, MA, 1988."},{"key":"BF01908629_CR4","doi-asserted-by":"crossref","unstructured":"M. H. Brown. Zeus: A system for algorithm animation. InProceedings of the 1991 IEEE Workshop on Visual Languages, pages 4\u20139, October 1991.","DOI":"10.1109\/WVL.1991.238857"},{"issue":"12","key":"BF01908629_CR5","first-page":"52","volume":"25","author":"M. H. Brown","year":"1992","unstructured":"M. H. Brown and J. Hershberger. Color and sound in algorithm animation.IEEE Trans, Comput., 25(12):52\u201363, 1992.","journal-title":"IEEE Trans, Comput."},{"key":"BF01908629_CR6","volume-title":"Technical Report CMU-CS-80-150","author":"B. M. Chazelle","year":"1980","unstructured":"B. M. Chazelle. Computational Geometry and Convexity. Technical Report CMU-CS-80-150, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1980."},{"key":"BF01908629_CR7","volume-title":"EATCS Monographs on Theoretical Computer Science, volume 10","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, volume 10. Springer-Verlag, Berlin, 1987."},{"key":"BF01908629_CR8","doi-asserted-by":"crossref","unstructured":"W. Franklin. Polygon properties calculated from the vertex neighborhoods. InProceedings of the 3rd ACM Symposium on Computational Geometry, pages 110\u2013118, 1987.","DOI":"10.1145\/41958.41969"},{"key":"BF01908629_CR9","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/0196-6774(83)90013-5","volume":"4","author":"R. L. Graham","year":"1983","unstructured":"R. L. Graham and F. F. Yao. Finding the convex hull of a simple polygon.J. Algorithms,4:324\u2013331, 1983.","journal-title":"J. Algorithms"},{"key":"BF01908629_CR10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"L. 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":"BF01908629_CR11","doi-asserted-by":"crossref","unstructured":"L. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry. InProceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 100\u2013111, 1983.","DOI":"10.1109\/SFCS.1983.1"},{"key":"BF01908629_CR12","volume-title":"Research Report Videotape 50b","author":"J. Hershberger","year":"1989","unstructured":"J. Hershberger and M. H. Brown. Boolean Formulae for Simple Polygons. Research Report Videotape 50b, DEC Systems Research Center, Palo Alto, CA, 1989."},{"key":"BF01908629_CR13","doi-asserted-by":"crossref","unstructured":"K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan. Sorting Jordan sequences in linear time. InProceedings of the ACM Symposium on Computational Geometry, pages 196\u2013203, 1985.","DOI":"10.1145\/323233.323259"},{"key":"BF01908629_CR14","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF00993195","volume":"12","author":"D. T. Lee","year":"1983","unstructured":"D. T. Lee. On finding the convex hull of a simple polygon.Internat. J. Comput. Inform. Sci., 12:87\u201398, 1983.","journal-title":"Internat. J. Comput. Inform. Sci."},{"key":"BF01908629_CR15","volume-title":"Digitial Logic and Computer Design","author":"M. M. Mano","year":"1979","unstructured":"M. M. Mano.Digitial Logic and Computer Design. Prentice-Hall, Englewood Cliffs, NJ, 1979."},{"key":"BF01908629_CR16","volume-title":"An Introduction to Solid Modeling","author":"M. M\u00e4ntyl\u00e4","year":"1987","unstructured":"M. M\u00e4ntyl\u00e4.An Introduction to Solid Modeling. Computer Science Press, Rockville, MD, 1987."},{"key":"BF01908629_CR17","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(79)90069-3","volume":"9","author":"D. McCallum","year":"1979","unstructured":"D. McCallum and D. Avis. A linear algorithm for finding the convex hull of a simple polygon.Inform. Process. Lett., 9:201\u2013206, 1979.","journal-title":"Inform. Process. Lett."},{"key":"BF01908629_CR18","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","volume":"25","author":"A. Melkman","year":"1987","unstructured":"A. Melkman. On-line construction of the convex hull of a simple polyline.Inform. Process. Lett., 25:11\u201312, 1987.","journal-title":"Inform. Process. Lett."},{"key":"BF01908629_CR19","volume-title":"Geometric Modeling","author":"M. Mortenson","year":"1985","unstructured":"M. Mortenson.Geometric Modeling. Wiley, New York, 1985."},{"key":"BF01908629_CR20","unstructured":"R. Newell. Solid modelling and parametric design in the Medusa system. InComputer Graphics '82, Proceedings of the Online Conference, pages 223\u2013235, 1982."},{"key":"BF01908629_CR21","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke.Art Gallery Theorems and Algorithms. Oxford University Press, Oxford, 1987."},{"key":"BF01908629_CR22","doi-asserted-by":"crossref","unstructured":"M. Paterson and F. Yao. Binary partitions with applications to hidden-surface removal and solid modelling. InProceedings of the 5th ACM Symposium on Computational Geometry, pages 23\u201332, 1989.","DOI":"10.1145\/73833.73836"},{"key":"BF01908629_CR23","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0031-3203(68)90006-X","volume":"1","author":"T. Pavlidis","year":"1968","unstructured":"T. Pavlidis. Analysis of set patterns.Pattern Recognition, 1:165\u2013178, 1968.","journal-title":"Pattern Recognition"},{"key":"BF01908629_CR24","volume-title":"SANDIA Report SAND84-0572","author":"D. Peterson","year":"1984","unstructured":"D. Peterson. Halfspace Representation of Extrusions, Solids of Revolution, and Pyramids. SANDIA Report SAND84-0572, Sandia National Laboratories, Albuquerque, NM, 1984."},{"key":"BF01908629_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos.Computational Geometry. Springer-Verlag, New York, 1985."},{"key":"BF01908629_CR26","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1145\/356827.356833","volume":"12","author":"A. Requicha","year":"1980","unstructured":"A. Requicha. Representations for rigid solids: Theory, methods, and systems.ACM Comput. Surveys, 12:437\u2013464, 1980.","journal-title":"ACM Comput. Surveys"},{"key":"BF01908629_CR27","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0196-6774(87)90028-9","volume":"8","author":"A. A. Sch\u00e4ffer","year":"1987","unstructured":"A. A. Sch\u00e4ffer and C. J. Van Wyk. Convex hulls of piecewise-smooth Jordan curves.J. Algorithms, 8:66\u201394, 1987.","journal-title":"J. Algorithms"},{"key":"BF01908629_CR28","doi-asserted-by":"crossref","unstructured":"W. Tiller. Rational B-splines for curve and surface representation.IEEE Comput. Graphics and Applications, 3, 1983.","DOI":"10.1109\/MCG.1983.263244"},{"issue":"4","key":"BF01908629_CR29","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1145\/357346.357348","volume":"3","author":"S. B. Tor","year":"1984","unstructured":"S. B. Tor and A. E. Middleditch. Convex decomposition of simple polygons.ACM Trans. Graphics, 3(4):244\u2013265, 1984.","journal-title":"ACM Trans. Graphics"},{"issue":"3","key":"BF01908629_CR30","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1145\/965139.807400","volume":"12","author":"H. Voelcker","year":"1978","unstructured":"H. Voelcker, A. Requicha, E. Hartquist, W. Fisher, J. Metzger, R. Tilove, N. Birrell, W. Hunt, G. Armstrong, T. Check, R. Moote, and J. McSweeney. The PADL-1.0\/2 system for defining and displaying solid objects.ACM Comput. Graphics, 12(3):257\u2013263, 1978.","journal-title":"ACM Comput. Graphics"},{"key":"BF01908629_CR31","doi-asserted-by":"crossref","unstructured":"J. R. Woodwark and A. F. Wallis, Graphical input to a Boolean solid modeller. InProceedings of CAD 82, pages 681\u2013688, Brighton, U.K., 1982.","DOI":"10.1016\/B978-0-86103-058-3.50078-6"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01908629.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01908629\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01908629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T16:18:57Z","timestamp":1735834737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01908629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["BF01908629"],"URL":"https:\/\/doi.org\/10.1007\/bf01908629","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}