{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:01Z","timestamp":1759638601800},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1994,12,1]],"date-time":"1994-12-01T00:00:00Z","timestamp":786240000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,12]]},"DOI":"10.1007\/bf01188718","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T05:55:44Z","timestamp":1108706144000},"page":"533-552","source":"Crossref","is-referenced-by-count":15,"title":["New results for the minimum weight triangulation problem"],"prefix":"10.1007","volume":"12","author":[{"given":"L. S.","family":"Heath","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. V.","family":"Pemmaraju","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Data Structures and Algorithms","author":"A. V. Aho","year":"1980","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman.Data Structures and Algorithms. Addison-Wesley, Reading, MA, 1980."},{"key":"CR2","unstructured":"E. Anagnostou. Progress in Minimum Weight Triangulation. Technical Report 232\/90, Department of Computer Science, University of Toronto, 1990."},{"key":"CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"CR4","unstructured":"P. D. Gilbert. New Results on Planar Triangulations. M.Sc. thesis, Report No. UILUENG 78 2243, University of Illinois, 1979."},{"key":"CR5","unstructured":"L. S. Heath and S. V. Pemmaraju. New Results for the Minimum Weight Triangulation Problem. Report No. TR 92-30, Department of Computer Science, Virginia Polytechnic Institute and State University, 1992."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(80)90062-9","volume":"10","author":"D. G. Kirkpatrick","year":"1980","unstructured":"D. G. Kirkpatrick, A note on Delaunay and optimal triangulations.Information Processing Letters,10, 1980, 127?128.","journal-title":"Information Processing Letters"},{"key":"CR7","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,2, 1987, 175?193.","journal-title":"Algorithmica"},{"key":"CR8","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 0(?n) lower bound for the non-optimality of the greedy triangulation.Information Processing Letters,25, 1987, 247?251.","journal-title":"Information Processing Letters"},{"key":"CR9","first-page":"238","volume-title":"Lecture Notes in Computer Science, Vol. 447","author":"C. Levcopoulos","year":"1990","unstructured":"C. Levcopoulos and A. Lingas. Fast algorithms for the greedy triangulation.Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 447, Springer-Verlag, Berlin, 1990, pp. 238?250."},{"key":"CR10","series-title":"Lecture Notes in Computer Science, Vol. 158","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/3-540-12689-9_110","volume-title":"Foundations of Computation Theory","author":"A. Lingas","year":"1983","unstructured":"A. Lingas. The greedy and Delaunay triangulations are not bad in the average case and minimum weight triangulation of multi-connected polygons is NP-complete.Foundations of Computation Theory, Lecture Notes in Computer Science, Vol. 158, Springer-Verlag, Berlin, 1983, pp. 270?284."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1137\/0608053","volume":"8","author":"A. Lingas","year":"1987","unstructured":"A. Lingas. A new heuristic for the minimum weight triangulation.SIAM Journal on Algebraic and Discrete Methods,8, 1987, 646?658.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"E. L. Lloyd. On triangulations of a set of points in the plane.Proceedings of the Eighteenth IEEE Symposium on Foundations of Computer Science, 1977, pp. 228?240.","DOI":"10.1109\/SFCS.1977.21"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0020-0190(79)90104-2","volume":"9","author":"G. K. Manacher","year":"1979","unstructured":"G. K. Manacher and A. L. Zobrist. Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation.Information Processing Letters,9, 1979, 31?34.","journal-title":"Information Processing Letters"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/0196-6774(87)90020-4","volume":"8","author":"D. A. Plaisted","year":"1987","unstructured":"D. A. Plaisted and J. Hong. A heuristic triangulation algorithm.Journal of Algorithms,8, 1987, 405?437.","journal-title":"Journal of Algorithms"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey. Closest point problems.Proceedings of the Sixteenth IEEE Symposium on Foundations of Computer Science, 1975, 151?162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"CR16","unstructured":"W. D. Smith. Studies in Computational Geometry Motivated by Mesh Generation. Ph.D. dissertation, Princeton University, 1989."},{"key":"CR17","volume-title":"Display and Analysis of Spatial Data","author":"P. Yoeli","year":"1975","unstructured":"P. Yoeli. Compilation of data for computer-assisted relief cartography. InDisplay and Analysis of Spatial Data, J. C. Davis and M. J. McCullagh, editors, Wiley, New York, 1975."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188718.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188718\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T12:41:47Z","timestamp":1556714507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["BF01188718"],"URL":"https:\/\/doi.org\/10.1007\/bf01188718","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}