{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T20:46:09Z","timestamp":1769719569280,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1992,4,1]],"date-time":"1992-04-01T00:00:00Z","timestamp":702086400000},"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":[[1992,4]]},"DOI":"10.1007\/bf02187846","type":"journal-article","created":{"date-parts":[[2005,10,29]],"date-time":"2005-10-29T08:58:18Z","timestamp":1130576298000},"page":"329-346","source":"Crossref","is-referenced-by-count":15,"title":["Polygon triangulation inO(n log logn) time with simple data structures"],"prefix":"10.1007","volume":"7","author":[{"given":"David G.","family":"Kirkpatrick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria M.","family":"Klawe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,9,6]]},"reference":[{"key":"BF02187846_CR1","volume-title":"A linear algorithm for determining the translation separability of two simple polygons","author":"B. K. Bhattacharya","year":"1986","unstructured":"Bhattacharya, B. K., and Toussaint, G. T., A linear algorithm for determining the translation separability of two simple polygons, Report SOCS-86.1, School Comput. Sci., McGill University, Montreal, 1986."},{"key":"BF02187846_CR2","doi-asserted-by":"crossref","unstructured":"Chazelle, B., A theorem on polygon cutting with applications,Proc. 23rd Annual Symp. on Foundations of Computer Science, 1982, pp. 339\u2013349.","DOI":"10.1109\/SFCS.1982.58"},{"key":"BF02187846_CR3","unstructured":"Chazelle, B., Triangulating a simple polygon in linear time, Princeton Tech. Report CS-TR-264-90, 1990."},{"key":"BF02187846_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/357337.357340","volume":"3","author":"B. Chazelle","year":"1984","unstructured":"Chazelle, B., and Incerpi, J., Triangulation and shape complexity,ACM Trans. Graphics 3 (1984), 135\u2013152.","journal-title":"ACM Trans. Graphics"},{"key":"BF02187846_CR5","doi-asserted-by":"crossref","unstructured":"Clarkson, K., Tarjan, R., and Van Wyk, C., A fast Las Vegas algorithm for triangulating a simple polygon,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 18\u201322 (Princeton Tech. Report CS-TR-157-88, 1988).","DOI":"10.1145\/73393.73396"},{"key":"BF02187846_CR6","volume-title":"Dynamic data structures for orthogonal intersection queries","author":"H. Edelsbrunner","year":"1980","unstructured":"H. Edelsbrunner, Dynamic data structures for orthogonal intersection queries, Report f59, Techn. Univ. Graz, Instit. Informationsverarb., Graz, 1980."},{"key":"BF02187846_CR7","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L. J., and Stolfi, J., Optimal point location in a monotone subdivision,SIAM J. Comput. 15 (1986), 317\u2013340.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"BF02187846_CR8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1145\/964967.801143","volume":"17","author":"E. Fiume","year":"1983","unstructured":"Fiume, E., Fournier, A., and Rudolph, L., A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultra-computer,ACM Trans. Comput. Graphics 17(3) (1983), 141\u2013150.","journal-title":"ACM Trans. Comput. Graphics"},{"key":"BF02187846_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"Fournier, A., and Montuno, D. Y., Triangulating simple polygons and equivalent problems,ACM Trans. Graphics 3 (1984), 153\u2013174.","journal-title":"ACM Trans. Graphics"},{"key":"BF02187846_CR10","doi-asserted-by":"crossref","unstructured":"Fung, K. Y., Nicholl, T. M., Tarjan, R. E., and Van Wyk, C. J., Simplified linear-time Jordan sorting and polygon clipping, Princeton Tech. Report CS-TR-189-88, 1988.","DOI":"10.21236\/ADA215110"},{"key":"BF02187846_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":"Garey, M. R. Johnson, D. S., Preparata, F. P., and Tarjan, R. E., Triangulating a simple polygon,Inform. Process. Lett. 7 (1978), 175\u2013180.","journal-title":"Inform. Process. Lett."},{"key":"BF02187846_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"Guibas, L., Hershberger, J., Leven, D., Sharir, M., and Tarjan, R. E., Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons,Algorithmica 2 (1987), 209\u2013233.","journal-title":"Algorithmica"},{"key":"BF02187846_CR13","series-title":"Lecture Notes on Computer Science","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/3-540-12689-9_105","volume-title":"Fast triangulation of a simple polygon","author":"S. Hertel","year":"1983","unstructured":"Hertel, S., and Mehlhorn, K., Fast triangulation of a simple polygon,Proc. Conf. on Foundations of Computer Theory, Lecture Notes on Computer Science, Vol. 158, Springer-Verlag, Berlin, 1983, pp. 207\u2013218."},{"key":"BF02187846_CR14","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"68","author":"K. Hoffman","year":"1986","unstructured":"Hoffman, K., Mehlhorn, K., Rosenstiehl P., and Tarjan R., Sorting Jordan sequences in linear time using level-linked search trees,Inform. and Control 68 (1986), 170\u2013184.","journal-title":"Inform. and Control"},{"key":"BF02187846_CR15","unstructured":"Keil, J. M., and Kirkpatrick, D. G., Computational geometry on integer gridsProc. 19th Annual Allerton Conference on Communication Control and Computing, 1981, pp. 41\u201350."},{"issue":"1","key":"BF02187846_CR16","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D. G., Optimal search in planar subdivisions,SIAM J. Comput. 12(1) (1983), 28\u201335.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"BF02187846_CR17","first-page":"34","volume":"15","author":"D. T. Lee","year":"1981","unstructured":"Lee, D. T., Shading of regions on vector display devices,ACM Trans. Comput. Graphics 15(3) (1981), 34\u201344.","journal-title":"ACM Trans. Comput. Graphics"},{"key":"BF02187846_CR18","doi-asserted-by":"crossref","unstructured":"Liou, W. T., Tan, J. J. M., and Lee, R. C. T., Minimum partitioning simple rectilinear polygons inO(n log logn) time,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 344\u2013353.","DOI":"10.1145\/73833.73871"},{"issue":"1","key":"BF02187846_CR19","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. E. Tarjan","year":"1988","unstructured":"Tarjan, R. E., and Van Wyk, C. J., AnO(n log logn)-time algorithm for triangulating a simple polygon,SIAM J. Comput. 17(1) (1988), 143\u2013178.","journal-title":"SIAM J. Comput."},{"key":"BF02187846_CR20","unstructured":"Toussaint, G., Pattern recognition and geometrical complexity,Proc. 5th Intern. Conf. on Pattern Recognition, 1980, pp. 1324\u20131347."},{"key":"BF02187846_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-009-3757-4_47","volume-title":"Computational geometry and morphology","author":"G. Toussaint","year":"1986","unstructured":"Toussaint, G., Computational geometry and morphology, Tech. Report SOCS-86.3, McGill University, Montreal, 1986."},{"key":"BF02187846_CR22","volume-title":"An output-complexity-sensitive polygon triangulation algorithm","author":"G. Toussaint","year":"1988","unstructured":"Toussaint, G., An output-complexity-sensitive polygon triangulation algorithm, Tech. Report SOCS-88.11, McGill University, Montreal, 1988."},{"key":"BF02187846_CR23","volume-title":"Computational Morphology","year":"1988","unstructured":"Toussaint, G. (ed.),Computational Morphology, North-Holland, Amsterdam, 1988."},{"issue":"1","key":"BF02187846_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0031-3203(82)90057-7","volume":"15","author":"G. Toussaint","year":"1982","unstructured":"Toussaint, G., and Avis, D., On a convex hull algorithm for polygons and its application to triangulation problems,Pattern Recognition 15(1) (1982), 23\u201329.","journal-title":"Pattern Recognition"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187846.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187846\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187846","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T07:06:51Z","timestamp":1683270411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,4]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,4]]}},"alternative-id":["BF02187846"],"URL":"https:\/\/doi.org\/10.1007\/bf02187846","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,4]]}}}