{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:40Z","timestamp":1725664720577},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_140","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:05Z","timestamp":1330292225000},"page":"296-308","source":"Crossref","is-referenced-by-count":1,"title":["A fast heuristic for approximating the minimum weight triangulation"],"prefix":"10.1007","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[]},{"given":"Drago","family":"Krznaric","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"G. Das and D. Joseph. Which triangulations approximate the complete graph. In Proc. Inter. Symp. on Optimal Algorithms, LNCS 401 (Springer, 1989) 168\u2013183.","DOI":"10.1007\/3-540-51859-2_15"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"M. T. Dickerson, R. L. S. Drysdale, S. A. McElfresh, and E. Welzl. Fast greedy triangulation algorithms. Proc. 10th ACM Symp. on Comp. Geom. (1994) 211\u2013220.","DOI":"10.1145\/177424.177649"},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02574002","volume":"11","author":"D. Eppstein","year":"1994","unstructured":"D. Eppstein. Approximating the minimum weight triangulation. Disc, and Comp. Geom. 11 (1994) 163\u2013191.","journal-title":"Disc, and Comp. Geom."},{"key":"26_CR4","series-title":"Master's thesis","volume-title":"New results in planar triangulations","author":"P. D. Gilbert","year":"1979","unstructured":"P. D. Gilbert. New results in planar triangulations. Master's thesis, Univ. of Illinois, Urbana, 1979."},{"key":"26_CR5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0190(89)90122-1","volume":"31","author":"S. Goldman","year":"1989","unstructured":"S. Goldman. A space efficient greedy triangulation algorithm. Infor. Proc. Lett. 31 (1989) 191\u2013196.","journal-title":"Infor. Proc. Lett."},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF01188718","volume":"12","author":"L. Heath","year":"1994","unstructured":"L. Heath and S. Pemmaraju. New results for the minimum weight triangulation problem. Algorithmica 12 (1994) 533\u2013552.","journal-title":"Algorithmica"},{"key":"26_CR7","series-title":"PhD thesis","volume-title":"Decomposing a Polygon into Simpler Components","author":"J. M. Keil","year":"1983","unstructured":"J. M. Keil. Decomposing a Polygon into Simpler Components. PhD thesis, Univ. of Toronto, Canada, 1983."},{"key":"26_CR8","first-page":"13","volume":"4","author":"J. M. Keil","year":"1994","unstructured":"J. M. Keil. Computing a subgraph of the minimum weight triangulation. Comp. Geom.: Theory & Appl. 4 (1994) 13\u201326.","journal-title":"Comp. Geom.: Theory & Appl."},{"key":"26_CR9","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. Infor. Proc. Lett. 10 (1980) 127\u2013128.","journal-title":"Infor. Proc. Lett."},{"key":"26_CR10","unstructured":"D. Krznaric and C. Levcopoulos. Computing a threaded quadtree from the Delaunay triangulation in linear time. In Proc. 7th CCCG (1995) 187\u2013192."},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"D. Krznaric and C. Levcopoulos. Computing hierarchies of clusters from the EMST in linear time. In Proc. 15th FST&TCS, LNCS 1026 (Springer, 1995) 443\u2013455.","DOI":"10.1007\/3-540-60692-0_66"},{"key":"26_CR12","unstructured":"C. Levcopoulos and D. Krznaric. The greedy triangulation can be computed from the Delaunay in linear time. Tech. Rep. LU-CS-TR:94-136, Lund Univ., 1994."},{"key":"26_CR13","unstructured":"C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proc. 7th SODA (1995) 392\u2013401."},{"key":"26_CR14","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0020-0190(95)00200-6","volume":"57","author":"C. Levcopoulos","year":"1996","unstructured":"C. Levcopoulos and D. Krznaric. Tight lower bounds for minimum weight triangulation heuristics. Infor. Proc. Lett. 57 (1996) 129\u2013135.","journal-title":"Infor. Proc. Lett."},{"key":"26_CR15","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/BF01994882","volume":"32","author":"C. Levcopoulos","year":"1992","unstructured":"C. Levcopoulos and A. Lingas. Fast algorithms for greedy triangulation. BIT 32 (1992) 280\u2013296.","journal-title":"BIT"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and A. Lingas. The greedy triangulation approximates the MWT and can be computed in linear time in the average case. In Proc. ICCI, LNCS 497 (Springer, 1991).","DOI":"10.1007\/3-540-54029-6_163"},{"key":"26_CR17","series-title":"PhD thesis","volume-title":"Advances in minimum weight triangulation","author":"A. Lingas","year":"1983","unstructured":"A. Lingas. Advances in minimum weight triangulation. PhD thesis, Link\u00f6ping Univ., Sweden, 1983."},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction (Springer, 1985).","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"26_CR19","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. J. of Algorithms 8 (1987) 405\u2013437.","journal-title":"J. of Algorithms"},{"key":"26_CR20","unstructured":"W. D. Smith. Studies in Computational Geometry Motivated by Mesh Generation. PhD thesis, Princeton Univ., 1989."},{"key":"26_CR21","unstructured":"C. A. Wang. An optimal algorithm for greedy triangulation of a set of points. In Proc. 6th CCCG (1994) 332\u2013338."},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"C. A. Wang and F. Chin. Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time. In Proc. 3rd ESA, LNCS 979 (Springer, 1995) 280\u2013294.","DOI":"10.1007\/3-540-60313-1_150"},{"key":"26_CR23","unstructured":"P. Yoeli. Compilation of data for computer-assisted relief cartography. In J. C. Davis and M. J. McCullagh, eds., Display and Analysis of Spatial Data (Wiley, 1975)."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_140.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:06:03Z","timestamp":1605647163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_140","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}