{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T22:25:11Z","timestamp":1769811911383,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1989,10,1]],"date-time":"1989-10-01T00:00:00Z","timestamp":623203200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1989,10]]},"DOI":"10.1007\/bf02187741","type":"journal-article","created":{"date-parts":[[2005,9,20]],"date-time":"2005-09-20T18:57:34Z","timestamp":1127242654000},"page":"423-432","source":"Crossref","is-referenced-by-count":37,"title":["A fast las vegas algorithm for triangulating a simple polygon"],"prefix":"10.1007","volume":"4","author":[{"given":"Kenneth L.","family":"Clarkson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher J.","family":"Van Wyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1989,10,1]]},"reference":[{"key":"BF02187741_CR1","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, R. Cole, and M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms,Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 151\u2013160.","DOI":"10.1109\/SFCS.1987.12"},{"key":"BF02187741_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/357337.357340","volume":"3","author":"B. Chazelle","year":"1984","unstructured":"B. Chazelle and J. Incerpi, Triangulation and shape complexity,ACM Transactions on Graphics,3 (1984), 135\u2013152.","journal-title":"ACM Transactions on Graphics"},{"key":"BF02187741_CR3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson, New applications of random sampling in computational geometry,Discrete and Computational Geometry,2 (1987), 195\u2013222.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02187741_CR4","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, Applications of random sampling in computational geometry, II,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 1\u201311.","DOI":"10.1145\/73393.73394"},{"key":"BF02187741_CR5","unstructured":"K. L. Clarkson, R. Cole, and R. E. Tarjan, private communication."},{"key":"BF02187741_CR6","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II,Discrete and Computational Geometry, this issue, 387\u2013421.","DOI":"10.1007\/BF02187740"},{"key":"BF02187741_CR7","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, R. E. Tarjan, and C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 18\u201322.","DOI":"10.1145\/73393.73396"},{"key":"BF02187741_CR8","volume-title":"Probabilistic Methods in Combinatorics","author":"P. Erdos","year":"1974","unstructured":"P. Erdos and J. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York, 1974."},{"key":"BF02187741_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Transactions on Graphics,3 (1984), 153\u2013174.","journal-title":"ACM Transactions on Graphics"},{"key":"BF02187741_CR10","doi-asserted-by":"crossref","unstructured":"K. Y. Fung, T. M. Nicholl, R. E. Tarjan, and C. J. Van Wyk, Simplified linear-time Jordan sorting and polygon clipping,ACM Transactions on Graphics, submitted.","DOI":"10.1016\/0020-0190(90)90111-A"},{"key":"BF02187741_CR11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Information Processing Letters,7 (1978), 175\u2013180.","journal-title":"Information Processing Letters"},{"key":"BF02187741_CR12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl,\u025b-nets and simplex range queries,Discrete and Computational Geometry,2 (1987), 127\u2013151.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02187741_CR13","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"68","author":"K. Hoffman","year":"1986","unstructured":"K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. Tarjan, Sorting Jordan sequences in linear time using level-linked search trees,Information and Control,68 (1986), 170\u2013184.","journal-title":"Information and Control"},{"key":"BF02187741_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"BF02187741_CR15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. E. Tarjan","year":"1988","unstructured":"R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-time algorithm for triangulating a simple polygon,SIAM Journal on Computing,17 (1988), 143\u2013178.","journal-title":"SIAM Journal on Computing"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187741.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187741\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T17:57:48Z","timestamp":1586455068000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["BF02187741"],"URL":"https:\/\/doi.org\/10.1007\/bf02187741","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,10]]}}}