{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:09:41Z","timestamp":1725574181367},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653844"},{"type":"electronic","value":"9783540493822"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/978-3-540-49382-2_21","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T23:37:34Z","timestamp":1294443454000},"page":"233-244","source":"Crossref","is-referenced-by-count":0,"title":["A Parallel Approximation Algorithm for Minimum Weight Triangulation"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"21_CR1","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02136025","volume":"24","author":"R.C. Chang","year":"1984","unstructured":"Chang, R.C., Lee, R.C.T.: On the average length of delaunay triangulations. BIT\u00a024(3), 269\u2013273 (1984)","journal-title":"BIT"},{"unstructured":"Gilbert, P.D.: New results in planar triangulations. Report R-850, Coordinated Sci. Lab., University of Illinois, Urbana, Illinois, USA (1979)","key":"21_CR2"},{"unstructured":"Gudmundsson, J., Levcopoulos, C.: A parallel approximation algorithm for minimum weight triangulation. Report LU-CS-TR:97-196, Dept. of Computer Science, Lund University, Lund, Sweden (1997)","key":"21_CR3"},{"issue":"3","key":"21_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(80)90062-9","volume":"10","author":"D.G. Kirkpatrick","year":"1987","unstructured":"Kirkpatrick, D.G.: A note on delaunay and optimal triangulations. Information Processing Letters\u00a010(3), 127\u2013128 (1987)","journal-title":"Information Processing Letters"},{"issue":"4","key":"21_CR5","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0020-0190(87)90170-0","volume":"25","author":"C. Levcopoulos","year":"1987","unstructured":"Levcopoulos, C.: An \u03c9 ( $\\sqrt{n}$ ) lower bound for the nonoptimality of the greedy triangulation. Information Processing Letters\u00a025(4), 247\u2013251 (1987)","journal-title":"Information Processing Letters"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithm Theory - SWAT \u201996","author":"C. Levcopoulos","year":"1996","unstructured":"Levcopoulos, C., Krznaric, D.: The greedy triangulation can be computed from the delaunay in linear time. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097. Springer, Heidelberg (1996)"},{"unstructured":"Levcopoulos, C., Krznaric, D.: Computing a threaded quadtree from the delaunay triangulation in linear time. In: Proc. 7th CCCG, pp. 187\u2013192 (1995)","key":"21_CR7"},{"unstructured":"Levcopoulos, C., Krznaric, D.: Quasi-greedy triangulations approximating the minimum weight triangulation. In: Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, pp. 392\u2013401 (1996)","key":"21_CR8"},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01840358","volume":"2","author":"C. Levcopoulos","year":"1987","unstructured":"Levcopoulos, C., Lingas, A.: On approximation behavior of the greedy triangulation for convex polygons. Algorithmica\u00a02(2), 175\u2013193 (1987)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Levcopoulos, C., Lingas, A.: Greedy triangulation approximates the optimum and can be implemented in linear time in the average case. In: Dehne, F., Fiala, F., Koczkodaj, W.W. (eds.) ICCI 1991. LNCS, vol.\u00a0497. Springer, Heidelberg (1991)","key":"21_CR10","DOI":"10.1007\/3-540-54029-6_163"},{"doi-asserted-by":"crossref","unstructured":"Levcopoulos, C., Lingas, A.: C-sensitive triangulations approximate the minmax lengthtri angulation. In: Shyamasundar, R.K. (ed.) FSTTCS 1992. LNCS, vol.\u00a0652. Springer, Heidelberg (1992)","key":"21_CR11","DOI":"10.1007\/3-540-56287-7_98"},{"doi-asserted-by":"crossref","unstructured":"Levcopoulos, C., Lingas, A., Wang, C.: On the parallel complexity of planar triangulations. In: Thiagarajan, P.S. (ed.) FSTTCS 1995. LNCS, vol.\u00a01026. Springer, Heidelberg (1995)","key":"21_CR12","DOI":"10.1007\/3-540-60692-0_64"},{"doi-asserted-by":"crossref","unstructured":"Merks, E.: An optimal parallel algorithm for triangulating a set of points in the plane. International Journal of Parallel Programming\u00a015(5) (1986)","key":"21_CR13","DOI":"10.1007\/BF01414464"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(87)90093-7","volume":"25","author":"C.A. Wang","year":"1987","unstructured":"Wang, C.A., Tsin, Y.H.: An o(log n) time parallel algorithm for triangulating a set of points in the plane. Information Processing Letters\u00a025, 55\u201360 (1987)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-49382-2_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:06:49Z","timestamp":1559916409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-49382-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653844","9783540493822"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-49382-2_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}