{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:09:57Z","timestamp":1770062997958,"version":"3.49.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01994882","type":"journal-article","created":{"date-parts":[[2005,8,4]],"date-time":"2005-08-04T16:22:09Z","timestamp":1123172529000},"page":"280-296","source":"Crossref","is-referenced-by-count":10,"title":["Fast algorithms for greedy triangulation"],"prefix":"10.1007","volume":"32","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994882_CR1","first-page":"388","volume":"39","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal,Research topics in computational geometry, Bulletin of EATCS 39 (October 1989), pp. 388\u2013408.","journal-title":"Bulletin of EATCS"},{"key":"BF01994882_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, L. Guibas, J. Saxe and P. Shor,A linear time algorithm for computing the Voronoi diagram of a convex polygon, in Proc. of the 19th ACM Symposium on Theory of Computing, New York, pp. 39\u201345, 1987.","DOI":"10.1145\/28395.28400"},{"key":"BF01994882_CR3","doi-asserted-by":"crossref","unstructured":"L. P. Chew,Constrained Delaunay triangulations, in: Proc. of the 3rd ACM Symposium on Computational Geometry, Waterloo, pp. 215\u2013222, 1987.","DOI":"10.1145\/41958.41981"},{"key":"BF01994882_CR4","volume-title":"New Results in Planar Triangulations","author":"P. D. Gilbert","year":"1979","unstructured":"P. D. Gilbert,New Results in Planar Triangulations, M.S. Thesis, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, 1979."},{"key":"BF01994882_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry, Texts and Monographs in Computer Science","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry, Texts and Monographs in Computer Science, Springer Verlag, Berlin, 1987."},{"key":"BF01994882_CR6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0190(89)90122-1","volume":"31","author":"S. A. Goldman","year":"1989","unstructured":"S. A. Goldman,A space efficient greedy triangulation algorithm, Information Processing Letters 31 (1989) pp. 191\u2013196.","journal-title":"Information Processing Letters"},{"key":"BF01994882_CR7","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(87)90170-0","volume":"25","author":"C. Levcopoulos","year":"1987","unstructured":"C. Levcopoulos,An \u0398(\u221an) lower bound for non-optimality of the greedy triangulation, Information Processing Letters 25 (1987), pp. 247\u2013251.","journal-title":"Information Processing Letters"},{"key":"BF01994882_CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02187695","volume":"1","author":"D. T. Lee","year":"1986","unstructured":"D. T. Lee and A. Lin,Generalized Delaunay Triangulation for Planar Graphs, Discrete and Computational Geometry 1 (1986), Springer Verlag, pp. 201\u2013217.","journal-title":"Discrete and Computational Geometry"},{"key":"BF01994882_CR9","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01840358","volume":"2","author":"C. Levcopoulos","year":"1987","unstructured":"C. Levcopoulos and A. Lingas,On approximation behavior of the greedy triangulation for convex polygons, Algorithmica (1987) 2, pp. 175\u2013193.","journal-title":"Algorithmica"},{"key":"BF01994882_CR10","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(89)90134-5","volume":"66","author":"C. Levcopoulos","year":"1989","unstructured":"C. Levcopoulos, A. Lingas and J. Sack,Heuristics for optimum binary search trees and minimum weight triangulation problems, Theoretical Computer Science 66 (1989), pp. 181\u2013203.","journal-title":"Theoretical Computer Science"},{"key":"BF01994882_CR11","first-page":"359","volume-title":"Lecture Notes in Control and Information Sciences, Vol. 113","author":"A. Lingas","year":"1987","unstructured":"A. Lingas,A space efficient algorithm for the greedy triangulation, in: M. Thoma and A. Wyner, eds., Proc. 13th IFIP Conf. on System Modelling and Optimization, Tokyo (August 1987), Lecture Notes in Control and Information Sciences, Vol. 113 (Springer, Berlin, 1987), pp. 359\u2013364."},{"key":"BF01994882_CR12","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/3-540-50728-0_48","volume":"344","author":"A. Lingas","year":"1988","unstructured":"A. Lingas,Greedy triangulation can be efficiently implemented in the average case, in: J. van Leeuwen, ed., Proc. International Workshop WG'88, Amsterdam (June 1988), Lecture Notes in Computer Science, Vol. 344 (Springer, Berlin, 1988), pp. 253\u2013261.","journal-title":"Lecture Notes in Computer Science"},{"key":"BF01994882_CR13","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0190(89)90043-4","volume":"32","author":"A. Lingas","year":"1989","unstructured":"A. Lingas,Voronoi diagrams with barriers and their applications, Information Processing Letters 32 (1989), pp. 191\u2013198.","journal-title":"Information Processing Letters"},{"key":"BF01994882_CR14","doi-asserted-by":"crossref","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, 1977.","DOI":"10.1109\/SFCS.1977.21"},{"key":"BF01994882_CR15","doi-asserted-by":"crossref","unstructured":"G. Manacher and A. Zorbrist,Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation, Information Processing Letters 9 (1979).","DOI":"10.1016\/0020-0190(79)90104-2"},{"key":"BF01994882_CR16","volume-title":"Computational Geometry, An Introduction, Texts and Monographs in Computer Science","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, An Introduction, Texts and Monographs in Computer Science, Springer Verlag, New York, 1985."},{"key":"BF01994882_CR17","doi-asserted-by":"crossref","unstructured":"C. Wang and L. Schubert,An optimal algorithm for constructing the Delaunay triangulation of a set of line segments, in: Proc of the 3rd ACM Symposium on Computational Geometry, Waterloo, pp. 223\u2013232, 1987.","DOI":"10.1145\/41958.41982"}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994882.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994882\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994882","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T17:56:31Z","timestamp":1557770191000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994882"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01994882"],"URL":"https:\/\/doi.org\/10.1007\/bf01994882","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}