{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T20:52:37Z","timestamp":1769719957408,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Visual Computer"],"published-print":{"date-parts":[[1991,9]]},"DOI":"10.1007\/bf01905693","type":"journal-article","created":{"date-parts":[[2005,7,29]],"date-time":"2005-07-29T19:15:34Z","timestamp":1122664534000},"page":"280-295","source":"Crossref","is-referenced-by-count":28,"title":["Efficient triangulation of simple polygons"],"prefix":"10.1007","volume":"7","author":[{"given":"Godfried","family":"Toussaint","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01905693_CR1","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1090\/S0002-9939-1951-0046635-9","volume":"2","author":"SS Cairns","year":"1951","unstructured":"Cairns SS (1951) An elementary proof of the Jordan-Schoenflies theorem. Proc Am Math Soc 2:860\u2013867","journal-title":"Proc Am Math Soc"},{"key":"BF01905693_CR2","first-page":"339","volume":"23","author":"B Chazelle","year":"1982","unstructured":"Chazelle B (1982) A theorem on polygon cutting with applications. Proc IEEE Symposium, on Foundations of Computer Science, Chicago. 23:339\u2013349","journal-title":"Proc IEEE Symposium, on Foundations of Computer Science, Chicago"},{"key":"BF01905693_CR3","unstructured":"Chazelle B (1990) Triangulating a simple polygon in linear time. Technical Report, CS-TR-264-90, Department of Computer Science, Princeton University"},{"key":"BF01905693_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/357337.357340","volume":"3","author":"B Chazelle","year":"1984","unstructured":"Chazelle B, Incerpi J (1984) Triangulation and shape complexity. ACM Trans Graph 3:135\u2013152","journal-title":"ACM Trans Graph"},{"key":"BF01905693_CR5","unstructured":"ElGindy HA (1985) A linear algorithm for triangulating weakly externally visible polygons. Technical Report MS-CIS-86-75, University of Pennsylvania"},{"key":"BF01905693_CR6","doi-asserted-by":"crossref","unstructured":"ElGindy H, Toussaint GT (1988) On triangulating palm polygons in linear time. Proc Comput Graph Int, Geneva. pp 308\u2013317.","DOI":"10.1007\/978-3-642-83492-9_27"},{"issue":"1\/2","key":"BF01905693_CR7","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/BF01901482","volume":"5","author":"H ElGindy","year":"1989","unstructured":"ElGindy H, Toussaint GT (1989) On geodesic properties of polygons relevant to lineartime triangulation. The Visual Computer 5(1\/2):68\u201374","journal-title":"The Visual Computer"},{"key":"BF01905693_CR8","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02263430","volume":"31","author":"H ElGindy","year":"1983","unstructured":"ElGindy H, Avis D, Toussaint GT (1983) Applications of a two-dimensional hiddenline algorithm to other geometric problems. Computing 31:191\u2013202","journal-title":"Computing"},{"key":"BF01905693_CR9","unstructured":"ElGindy H, Everett H, Toussaint GT (1991) Slicing an ear in linear time. Pattern Recognition Letters (in press)"},{"key":"BF01905693_CR10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A Fournier","year":"1984","unstructured":"Fournier A, Montuno DY (1984) Triangulating simple polygons and equivalent problems. ACM Trans Graph 3:153\u2013174","journal-title":"ACM Trans Graph"},{"key":"BF01905693_CR11","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1109\/T-C.1975.224276","volume":"24","author":"H-YF Feng","year":"1975","unstructured":"Feng H-YF, Pavlidis T (1975) Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition. IEEE Trans Comput C 24:636\u2013650","journal-title":"IEEE Trans Comput C"},{"key":"BF01905693_CR12","unstructured":"Forder HG (1927) The foundations of Euclidean geometry. Cambridge University Press"},{"key":"BF01905693_CR13","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"MR Garey","year":"1978","unstructured":"Garey MR, Johnson DS, Preparata FP, Tarjan RE (1978) Triangulating a simple polygon. Inf Proc Lett 7:175\u2013179","journal-title":"Inf Proc Lett"},{"key":"BF01905693_CR14","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Proc Lett 1:132\u2013133","journal-title":"Inf Proc Lett"},{"key":"BF01905693_CR15","first-page":"207","volume":"158","author":"S Hertel","year":"1983","unstructured":"Hertel S, Mehlhorn K (1983) Fast triangulation of simple polygons. Proc FCT, LNCS 158:207\u2013215","journal-title":"Proc FCT, LNCS"},{"key":"BF01905693_CR16","doi-asserted-by":"crossref","first-page":"132","DOI":"10.2307\/3616677","volume":"59","author":"W-C Ho","year":"1975","unstructured":"Ho W-C (1975) Decomposition of a polygon into triangles. The mathematical gazette 59:132\u2013134","journal-title":"The mathematical gazette"},{"key":"BF01905693_CR17","doi-asserted-by":"crossref","unstructured":"Honsberger R (1970) Ingenuity in mathematics, Random House","DOI":"10.5948\/UPO9780883859384"},{"key":"BF01905693_CR18","doi-asserted-by":"crossref","unstructured":"Kong X, Everett H, Toussaint GT (1991) The Grahan scan triangulates simple polygons. Pattern Recognition Letters (in press)","DOI":"10.1016\/0167-8655(90)90089-K"},{"key":"BF01905693_CR19","unstructured":"Kirkpatrick DG, Klawe MM, Tarjan RE (1990)O(n log logn) polygon triangulation with simple data structures. Symposium on Computational Geometry, Berkeley, California. 6:34\u201343"},{"key":"BF01905693_CR20","volume-title":"Theory of functions, Part I. (Translated by F. Bagemihl from the 5th German edition)","author":"K Knopp","year":"1945","unstructured":"Knopp K (1945) Theory of functions, Part I. (Translated by F. Bagemihl from the 5th German edition) Dover; New York"},{"key":"BF01905693_CR21","unstructured":"Knopp K (1970) Funktionentheorie I., Sammlung G\u00f6schen Band 668. Walter de Gruyter"},{"key":"BF01905693_CR22","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1080\/00207168708803587","volume":"22","author":"SH Lee","year":"1987","unstructured":"Lee SH, Chwa KY (1987) A new triangulation linear class of simple polygons. Int J Comput Math 22:135\u2013147","journal-title":"Int J Comput Math"},{"key":"BF01905693_CR23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.2307\/2369986","volume":"33","author":"NJ Lennes","year":"1911","unstructured":"Lennes NJ (1911) Theorems on the simple finite polygon and polyhedron. Am J Math 33:37\u201362","journal-title":"Am J Math"},{"key":"BF01905693_CR24","volume-title":"Geometry: modern mathematics via the Euclidean plane","author":"LS Levy","year":"1970","unstructured":"Levy LS (1970) Geometry: modern mathematics via the Euclidean plane. Prindle, Weber and Schmidt, Boston"},{"key":"BF01905693_CR25","volume-title":"Fractals: form, chance, and dimension","author":"BB Mandelbrot","year":"1977","unstructured":"Mandelbrot BB (1977) Fractals: form, chance, and dimension. Freeman, San Francisco"},{"key":"BF01905693_CR26","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1080\/00029890.1975.11993898","volume":"82","author":"GH Meisters","year":"1975","unstructured":"Meisters GH (1975) Polygons have ears. Am Math Monthly 82:648\u2013651","journal-title":"Am Math Monthly"},{"key":"BF01905693_CR27","first-page":"380","volume":"5","author":"J Rupert","year":"1989","unstructured":"Rupert J, Seidel R (1989) On the difficulty of tetrahedralizing 3-dimensional non-convex polyhedra. ACM Symp Computational Geometry, Saarbr\u00fccken. 5:380\u2013392","journal-title":"ACM Symp Computational Geometry, Saarbr\u00fccken"},{"key":"BF01905693_CR28","unstructured":"Schoone AA, van Leeuwen J (1980) Triangulating a star-shaped polygon. Technical Report RUV-CS-80-3, University of Utrecht"},{"key":"BF01905693_CR29","unstructured":"Shermer T (1988) Computing bushy and thin triangulations. In: Toussaint GT (ed) Snapshots of computational and discrete geometry, Technical Report SOCS-88. 11, pp 119\u2013133"},{"key":"BF01905693_CR30","unstructured":"Shermer T (1988) Generating anthropomorphick-sprials. In: Toussaint GT (ed) Snaphshots of computational and discrete geometry, Technical Report SOCS-88.11, pp 233\u2013244"},{"key":"BF01905693_CR31","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0167-8655(84)90039-4","volume":"2","author":"GT Toussaint","year":"1984","unstructured":"Toussaint GT (1984) A new linear algorithm for triangulating monotone polygons. Pattern Recognition Lett 2:155\u2013158","journal-title":"Pattern Recognition Lett"},{"key":"BF01905693_CR32","doi-asserted-by":"crossref","first-page":"31","DOI":"10.2307\/2324033","volume":"98","author":"GT Toussant","year":"1991","unstructured":"Toussant, GT (1991) Anthropomorphic polygons. Am Math Monthly 98:31\u201335","journal-title":"Am Math Monthly"},{"key":"BF01905693_CR33","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/B978-0-444-87877-9.50015-7","volume-title":"Pattern recognition in practice II","author":"GT Toussaint","year":"1986","unstructured":"Toussaint GT (1986) New results in computational geometry relevant to pattern recognition in practice. In: Gelsema ES, Kanal LN (eds) Pattern recognition in practice II. North-Holland, Amsterdam, pp 135\u2013146"},{"key":"BF01905693_CR34","volume-title":"Computational morphology","year":"1988","unstructured":"Toussaint GT (ed) (1988) Computational morphology. North-Holland, Amsterdam"},{"issue":"1","key":"BF01905693_CR35","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0031-3203(82)90057-7","volume":"15","author":"GT Toussaint","year":"1982","unstructured":"Toussaint GT, Avis D (1982) On a convex hull algorithm for polygons and its application to triangulation problems. Pattern Recognition Letters 15(1):23\u201329","journal-title":"Pattern Recognition Letters"},{"key":"BF01905693_CR36","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"RE Tarjan","year":"1988","unstructured":"Tarjan RE, Van Wyk CJ (1988) AnO(n log logn)-time algorithm for triangulating simple polygons. SIAM J Comput 17:143\u2013178","journal-title":"SIAM J Comput"},{"key":"BF01905693_CR37","first-page":"60","volume":"4","author":"TC Woo","year":"1985","unstructured":"Woo TC, Shin SY (1985) A linear time algorithm for triangulating a point-visible polygon. ACM Trans Graph 4:60\u201370","journal-title":"ACM Trans Graph"},{"key":"BF01905693_CR38","unstructured":"Yashiro H, Takahashi T, Takikawa K (1989) AnO(n(1+t 0)) algorithm for a simple polygon triangulation and its evaluation. IEICE Technical Report PRU-89-41"}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01905693.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01905693\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01905693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T12:19:52Z","timestamp":1586348392000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01905693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":38,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF01905693"],"URL":"https:\/\/doi.org\/10.1007\/bf01905693","relation":{},"ISSN":["0178-2789","1432-8726"],"issn-type":[{"value":"0178-2789","type":"print"},{"value":"1432-8726","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}