{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:12Z","timestamp":1725663372666},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540507284"},{"type":"electronic","value":"9783540460763"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-50728-0_48","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:32:22Z","timestamp":1330201942000},"page":"253-261","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Greedy triangulation can be efficiently implemented in the average case"],"prefix":"10.1007","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"17_CR1","unstructured":"D. Angluin and L.G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Proc. 9th Ann. ACM Symp. on Theory of Computing, New York."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"J.L. Bentley, B.W. Weide, A.C. Yao, Optimal expected-time algorithms for closest point problems, ACM Transactions on Mathematical Software 6, pp. 563\u2013580.","DOI":"10.1145\/355921.355927"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"R.C. Chang and R.C.T Lee, On the average length of Delaunay triangulations, BIT 24, pp. 269\u2013273.","DOI":"10.1007\/BF02136025"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"A. Fournier and D.Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics 3(2), pp. 153174.","DOI":"10.1145\/357337.357341"},{"key":"17_CR5","unstructured":"P.D. Gilbert, New Results in Planar Triangulations, M.S. Thesis, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick, A Note on Delaunay and Optimal Triangulations, IPL, Vol. 10, No. 3, pp. 127\u2013131.","DOI":"10.1016\/0020-0190(80)90062-9"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"A. Lingas, The greedy and Delaunay triangulations are not bad in the average case, IPL 22, pp. 25\u201331.","DOI":"10.1016\/0020-0190(86)90038-4"},{"key":"17_CR8","unstructured":"A. Lingas, The shortest diagonal problem, submitted to IPL."},{"key":"17_CR9","unstructured":"A. Lingas, A space efficient algorithm for the greedy triangulation, presented at the 13th IFIP Conference on System Modelling and Optimization, Tokyo, Japan 1987."},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and A. Lingas, On Approximation Behavior and Implementation of the Greedy Triangulation for Convex Polygons, Algorithmica 2, pp. 175193.","DOI":"10.1007\/BF01840358"},{"key":"17_CR11","unstructured":"E.L. Lloyd, On Triangulations of a Set of Points in the Plane, Proc. of the 18th Annual IEEE Conference on the Foundations of Computer Science, Providence."},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"G.K. Manacher, and A.L. Zorbrist, Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation, Information Processing Letters, Vol.9, No. 1, pp. 31\u201334.","DOI":"10.1016\/0020-0190(79)90104-2"},{"key":"17_CR13","unstructured":"G.K. Manacher, and A.L. Zorbrist, The use of probabilistic methods and of heaps for fast-average-case, space-optimal greedy algorithms, manuscript, 1982."},{"key":"17_CR14","unstructured":"K. Mehlhorn, Data Structures and Algorithms, EATS Monographs on Theoretical Computer Science, Springer Verlag, New York."},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"J. O'Rourke, The Computational Geometry Column, ACM SIGACT News 18(1).","DOI":"10.1145\/379139.379167"},{"key":"17_CR16","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry, An Introduction, Texts and Monographs in Computer Science, Springer Verlag, New York."},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"C. Wang and L. Shubert, An optimal algorithm for constructing the Delaunay triangulation of a set of line segments, in the proceedings of the 3rd ACM Symposium on Computational Geometry, Waterloo, pp. 223\u2013232, 1987.","DOI":"10.1145\/41958.41982"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50728-0_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:23:26Z","timestamp":1578525806000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_48"}},"subtitle":["detailed abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}