{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T15:38:04Z","timestamp":1743003484215,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":76,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_475","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:10:42Z","timestamp":1219662642000},"page":"2757-2764","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Triangulations"],"prefix":"10.1007","author":[{"given":"Franz","family":"Aurenhammer","sequence":"first","affiliation":[]},{"given":"Yinfeng","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"475_CR1_475","doi-asserted-by":"crossref","first-page":"1621","DOI":"10.1137\/S0097539702411368","volume":"32","author":"O Aichholzer","year":"2003","unstructured":"Aichholzer O, Aurenhammer F, Brass P, Krasser H (2003)\nPseudotriangulations from surfaces and a\u00a0novel type of edge flip.  SIAM J\nComput 32:1621\u20131653","journal-title":"SIAM J Comput"},{"key":"475_CR2_475","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF02712872","volume":"16","author":"O Aichholzer","year":"1996","unstructured":"Aichholzer O, Aurenhammer F, Cheng SW, Katoh N, Rote G,\nTaschwer M, Xu YF (1996) Triangulations intersect nicely. Discret Comput\nGeom 16:339\u2013359","journal-title":"Discret Comput Geom"},{"key":"475_CR3_475","unstructured":"Aichholzer O,\nAurenhammer F, Hackl T, Speckmann\u00a0B (2007) On (pointed) minimun weight\npseudo-triangulations.  In: Proc 19th Canadian Conf Computational Geom 3:209\u2013212"},{"key":"475_CR4_475","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF02712872","volume":"16","author":"O Aichholzer","year":"1996","unstructured":"Aichholzer O,\nAurenhammer F, Cheng S-W, Katoh N, Rote G, Taschwer M, Xu Y-F (1996)\n\t  Triangulations intersect nicely. Discret Comput Geometr 16:339\u2013359","journal-title":"Discret Comput Geometr"},{"key":"475_CR5_475","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1023\/A:1009776619164","volume":"2","author":"O Aichholzer","year":"1999","unstructured":"Aichholzer O, Aurenhammer F, Rote G, Xu YF (1999)\nConstant-level greedy triangulations approximate the MWT well.  J\u00a0Comb Optim\n2:361\u2013369","journal-title":"J Comb Optim"},{"key":"475_CR6_475","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s00373-007-0750-z","volume":"23","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer O,\nHackl T, Huemer C, Hurtado F, Krasser H, Vogtenhuber B (2007) On the number of plane\ngeometric graphs. Graphs Combin 23:467\u2013479","journal-title":"Graphs Combin"},{"key":"475_CR7_475","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0925-7721(93)90016-Y","volume":"3","author":"E Anagnostou","year":"1993","unstructured":"Anagnostou E, Corneil D (1993) Polynomial-time instances of the\nminimum weight triangulation problem. Comput Geom: Theory Appl 3:247\u2013259","journal-title":"Comput Geom: Theory Appl"},{"key":"475_CR8_475","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer F (1991) Voronoi diagrams\u00a0\u2013 a\u00a0survey of \na\u00a0fundamental geometric data structure. ACM Comput Surv 23:345\u2013405","journal-title":"ACM Comput Surv"},{"key":"475_CR9_475","doi-asserted-by":"crossref","unstructured":"Belleville P,\nKeil M, McAllister M, Snoeyink J (1996) On computing edges that are in all\nminimum-weight triangulations.  In: Proc. 12th Ann. ACM Symp. on Computational\nGeometry, pp V7\u2013V8","DOI":"10.1145\/237218.237425"},{"key":"475_CR10_475","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02573962","volume":"10","author":"M Bern","year":"1993","unstructured":"Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan TS (1993)\nEdge insertion for optimal triangulations.  Discret Comput Geom 10:47\u201365","journal-title":"Discret Comput Geom"},{"key":"475_CR11_475","first-page":"47","volume-title":"Computing in Euclidean Geometry, Lecture Notes Series in Computing 4","author":"M Bern","year":"1995","unstructured":"Bern M, Eppstein D (1995) Mesh generation and optimal\ntriangulation. In: Du DZ, Hwang FK (eds) Computing in Euclidean Geometry,\nLecture Notes Series in Computing 4. World Scientific, Singapore, pp 47\u2013123"},{"key":"475_CR12_475","doi-asserted-by":"crossref","unstructured":"Bern M, Eppstein D, Gilbert J (1990) Provably good mesh\ngeneration. In: Proc. 31st IEEE Symp. on Foundations of Computer Science, pp\n231\u2013241","DOI":"10.1109\/FSCS.1990.89542"},{"issue":"6","key":"475_CR13_475","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1142\/S0218195902000979","volume":"12","author":"P Bose","year":"1996","unstructured":"Bose P, Devroye L, Evans W (1996) Diamonds are not a\u00a0minimum\nweight triangulation's best friend. Int J Comput Geometr 12(6):445\u2013453","journal-title":"Int J Comput Geometr"},{"key":"475_CR14_475","unstructured":"Cheng SW, Golin MJ, Tsang JCF (1995) Expected-case\nanalysis of \u03b2-skeletons with applications to the construction of\nminimum-weight triangulations. In: Proc. 7th Canadian Conf. on\nComputational Geometry, pp 279\u2013283"},{"key":"475_CR15_475","doi-asserted-by":"crossref","unstructured":"Cheng SW, Katoh N, Sugai M (1996) A\u00a0study of the\nLMT-skeleton. In: Proc. Int. Symp. on Algorithms and Computation (ISAAC).\nLecture Notes in Computer Science, vol\u00a01178. Springer, pp\n256\u2013265","DOI":"10.1007\/BFb0009502"},{"key":"475_CR16_475","doi-asserted-by":"crossref","unstructured":"Cheng SW, Xu\nYF (1995) Constrained independence system and triangulations of planar point\nsets. In: Computing and Combinatorics, Proc. 1st Ann. Int. Conf. COCOON,\nLecture Notes in Computer Science, vol\u00a0959. Springer,\npp\u00a041\u201350","DOI":"10.1007\/BFb0030818"},{"key":"475_CR17_475","doi-asserted-by":"crossref","unstructured":"Cheng SW, Xu\nYF (1996) Approaching the largest \u03b2\u2011skeleton within a\u00a0minimum-weight\ntriangulation. In: Proc. 12th Ann. ACM Symp. on Computational Geometry,\npp\u00a0196\u2013203","DOI":"10.1145\/237218.237360"},{"key":"475_CR18_475","doi-asserted-by":"crossref","unstructured":"Das G,\nJoseph G (1989) Which triangulations approximate the complete graph?  Optimal\nAlgorithms, Lecture Notes in Computer Science, vol\u00a0401. Springer,\npp\u00a0168\u2013192","DOI":"10.1007\/3-540-51859-2_15"},{"key":"475_CR19_475","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0910064","volume":"10","author":"EF D'Azevedo","year":"1989","unstructured":"D'Azevedo EF, Simpson RB (1989) On optimal interpolation\ntriangle incidences. SIAM J Sci Statist Comput 10:1063\u20131075","journal-title":"SIAM J Sci Statist Comput"},{"key":"475_CR20_475","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF02153649","volume":"3","author":"L De Floriani","year":"1987","unstructured":"De Floriani L (1987) Surface representation based on triangular\ngrids. Visual Comput 3:27\u201350","journal-title":"Visual Comput"},{"key":"475_CR21_475","unstructured":"Dey TK, Dillencourt MB, Ghosh SK (1994) Triangulating with high\nconnectivity. In: Proc. 6th Canadian Conf. on Computational Geometry, pp\n339\u2013343"},{"key":"475_CR22_475","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0925-7721(97)89149-3","volume":"8","author":"MT Dickerson","year":"1997","unstructured":"Dickerson MT, Drysdale RLS, McElfresh SA, Welzl E (1997) Fast\nGreedy Triangulation Algorithms. Comput Geom: Theory Appl 8:67\u201386","journal-title":"Comput Geom: Theory Appl"},{"key":"475_CR23_475","doi-asserted-by":"crossref","unstructured":"Dickerson MT, McElfresh SA, Montague MH (1995) New algorithms\nand empirical findings on minimum weight triangulation heuristics.  In:\nProc. 11th Ann. ACM Symp. on Computational Geometry, pp 238\u2013247","DOI":"10.1145\/220279.220305"},{"key":"475_CR24_475","doi-asserted-by":"crossref","unstructured":"Dickerson MT, Montague MH (1996) A\u00a0(usually?) connected subgraph\nof the minimum weight triangulation. In: Proc. 12th Ann. ACM Symp. on\nComputational Geometry, pp\u00a0204\u2013213","DOI":"10.1145\/237218.237364"},{"key":"475_CR25_475","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/BF02187810","volume":"5","author":"MB Dillencourt","year":"1990","unstructured":"Dillencourt MB (1990) Toughness and Delaunay triangulations.\nDiscret Comput Geom 5:575\u2013601","journal-title":"Discret Comput Geom"},{"key":"475_CR26_475","volume-title":"A simple linear time greedy triangulation algorithm for uniformly distributed points","author":"RLS Drysdale","year":"1995","unstructured":"Drysdale RLS, Rote G, Aichholzer O (1995) A\u00a0simple linear time\ngreedy triangulation algorithm for uniformly distributed points. Graz Univ of\nTechnology, Graz, Austria"},{"key":"475_CR27_475","volume-title":"Algorithms in Combin Geometry, EATCS Monographs on Theoretical Computer Science 10","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner H (1987) Algorithms in Combin Geometry, EATCS\nMonographs on Theoretical Computer Science 10. Springer, Heidelberg"},{"key":"475_CR28_475","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01975867","volume":"15","author":"H Edelsbrunner","year":"1996","unstructured":"Edelsbrunner H, Shah NR (1996) Incremental topological flipping\nworks for regular triangulations. Algorithmica 15:223\u2013241","journal-title":"Algorithmica"},{"key":"475_CR29_475","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1137\/0222036","volume":"22","author":"H Edelsbrunner","year":"1993","unstructured":"Edelsbrunner H, Tan TS (1993) A\u00a0quadratic time algorithm for the\nminmax length triangulation. SIAM J Comput 22:527\u2013551","journal-title":"SIAM J Comput"},{"key":"475_CR30_475","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0913058","volume":"13","author":"H Edelsbrunner","year":"1992","unstructured":"Edelsbrunner H, Tan TS, Waupotitsch R (1992) An $$ { O(N^2 \\log N) } $$\ntime algorithm for the minmax angle triangulation. SIAM J Sci Statist Comput\n13:994\u20131008","journal-title":"SIAM J Sci Statist Comput"},{"key":"475_CR31_475","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0925-7721(92)90013-I","volume":"1","author":"D Eppstein","year":"1992","unstructured":"Eppstein D\n(1992) The farthest point Delaunay triangulation minimizes angles. Comput\nGeom: Theory Appl\n1:143\u2013148","journal-title":"Comput Geom: Theory Appl"},{"key":"475_CR32_475","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02574002","volume":"11","author":"D Eppstein","year":"1994","unstructured":"Eppstein D\n(1994) Approximating the minimum weight steiner triangulation. Discret Comput\nGeom 11:163\u2013194","journal-title":"Discret Comput Geom"},{"key":"475_CR33_475","doi-asserted-by":"crossref","unstructured":"Eppstein D\n(1999) Spanning trees and spanners. In: Sack JR, Urrutia J (eds) Handbook of\nComputational Geometry. Elsevier, pp\u00a0425\u2013461","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"475_CR34_475","first-page":"225","volume-title":"Computing in Euclidean Geometry, Lecture Notes Series in Computing 4","author":"S Fortune","year":"1995","unstructured":"Fortune S (1995) Voronoi Diagrams and Delaunay Triangulations.\nIn: Du DZ, Hwang FK (eds) Computing in Euclidean Geometry, Lecture Notes\nSeries in Computing 4. World Scientific, Singapore, pp 225\u2013265"},{"key":"475_CR35_475","unstructured":"Garey M,\nJohnson D (1979) Computers and Intractability. A\u00a0Guide to the Theory of\nNP-completeness. W.H. Freeman"},{"key":"475_CR36_475","unstructured":"Gilbert PD (1979) New results in planar triangulation.\nM.S. thesis, Coordinated Science Laboratory, University of Illinois, Urbana"},{"key":"475_CR37_475","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0020-0190(99)00018-6","volume":"69","author":"R Hainz","year":"1999","unstructured":"Hainz R, Aichholzer O, Aurenhammer F (1999) New results on MWT\nsubgraphs. Inf Process Lett 69:215\u2013219","journal-title":"Inf Process Lett"},{"key":"475_CR38_475","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF01188718","volume":"12","author":"LS Heath","year":"1994","unstructured":"Heath LS, Pemmaraju SV (1994) New results for the minimum weight\ntriangulation problem. Algorithmica 12:533\u2013552","journal-title":"Algorithmica"},{"key":"475_CR39_475","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0925-7721(93)90003-O","volume":"3","author":"K Jansen","year":"1993","unstructured":"Jansen K (1993) One strike against the min-max degree\ntriangulation problem. Comput Geom: Theory Appl 3:107\u2013120","journal-title":"Comput Geom: Theory Appl"},{"key":"475_CR40_475","unstructured":"Jaromczyk JW, Kowaluk M, Yao F (2007) An optimal algorithm for\nconstructing \u03b2-skeletons in the Lp-metric. SIAM J Comput, to\nappear"},{"key":"475_CR41_475","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(94)90014-0","volume":"4","author":"M Keil","year":"1994","unstructured":"Keil M (1994) Computing a\u00a0subgraph of the minimum weight\ntriangulation. Comput Geom: Theory Appl 4:13\u201326","journal-title":"Comput Geom: Theory Appl"},{"key":"475_CR42_475","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(80)90062-9","volume":"10","author":"DG Kirkpatrick","year":"1980","unstructured":"Kirkpatrick DG (1980) A\u00a0note on Delaunay and optimal\ntriangulations. Inf Proc Lett 10:127\u2013128","journal-title":"Inf Proc Lett"},{"key":"475_CR43_475","doi-asserted-by":"crossref","unstructured":"Kirkpatrick DG, Radke JD (1985) A\u00a0framework for computational\nmorphology In: Toussaint GT (ed) Computational Geometry, Elsevier, Amsterdam\npp 217\u2013248","DOI":"10.1016\/B978-0-444-87806-9.50013-X"},{"key":"475_CR44_475","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0167-5060(08)70048-7","volume":"9","author":"GT Klincsek","year":"1980","unstructured":"Klincsek GT (1980) Minimal triangulations of polygonal domains.\nAnnals Discret Math 9:127\u2013128","journal-title":"Annals Discret Math"},{"key":"475_CR45_475","unstructured":"Lambert T (1994) Empty-shape Triangulation Algorithms. Dept. of\nComputer Science, Univ. of Manitoba, Winnipeg, MB"},{"key":"475_CR46_475","unstructured":"Lambert T (1994) The Delaunay triangulation maximizes the mean\ninradius. In: Proc. 6th Canadian Conf. on Computational Geometry, pp\n201\u2013206"},{"key":"475_CR47_475","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/B978-0-12-587260-7.50011-X","volume-title":"Mathematical Software III","author":"CL Lawson","year":"1977","unstructured":"Lawson CL (1977) Software for C\n                        1 surface interpolation.\nIn: Rice JR (ed) Mathematical Software III. Academic Press, New York, pp\n161\u2013194"},{"key":"475_CR48_475","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02187695","volume":"1","author":"DT Lee","year":"1986","unstructured":"Lee DT, Lin AK (1986) Generalized Dekaunay triangulation for\nplanar graphs. Discret Comput Geom 1:201\u2013217","journal-title":"Discret Comput Geom"},{"key":"475_CR49_475","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(87)90170-0","volume":"25","author":"C Levcopoulos","year":"1987","unstructured":"Levcopoulos C (1987) An $$ { \\Omega(\\sqrt(n)) } $$ lower bound for\nnon-optimality of the greedy triangulation. Inf Process Lett 25:247\u2013251","journal-title":"Inf Process Lett"},{"key":"475_CR50_475","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1006\/jagm.1997.0918","volume":"27","author":"C Levcopoulos","year":"1998","unstructured":"Levcopoulos C, Krznaric D (1998) Quasi-greedy triangulations\napproximating the minimum weight triangulation. J\u00a0Algorithms 27:303\u2013338","journal-title":"J Algorithms"},{"key":"475_CR51_475","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01840358","volume":"2","author":"C Levcopoulos","year":"1987","unstructured":"Levcopoulos\nC, Lingas A (1987) On approximation behavior of the greedy triangulation\nfor convex polygons. Algorithmica 2:175\u2013193","journal-title":"Algorithmica"},{"key":"475_CR52_475","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/BF01994882","volume":"32","author":"C Levcopoulos","year":"1992","unstructured":"Levcopoulos C, Lingas A (1992) Fast algorithms for greedy\ntriangulation. BIT 32:280\u2013296","journal-title":"BIT"},{"key":"475_CR53_475","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1137\/0608053","volume":"8","author":"A Lingas","year":"1987","unstructured":"Lingas A (1987) A\u00a0new heuristic for the minimum weight\ntriangulation. SIAM J Algebr Discret Methods 8:646\u2013658","journal-title":"SIAM J Algebr Discret Methods"},{"key":"475_CR54_475","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0190(86)90038-4","volume":"22","author":"A Lingas","year":"1986","unstructured":"Lingas A (1986) The greedy and Delaunay triangulations are not\nbad in the average case. Inf Process Lett 22:25\u201331","journal-title":"Inf Process Lett"},{"key":"475_CR55_475","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0925-7721(94)90018-3","volume":"4","author":"A Lingas","year":"1994","unstructured":"Lingas A (1994) A\u00a0linear-time construction of the relative\nneighborhood graph from the Delaunay triangulation. Comput Geom: Theory Appl\n4:199\u2013208","journal-title":"Comput Geom: Theory Appl"},{"key":"475_CR56_475","doi-asserted-by":"crossref","unstructured":"Lloyd EL (1977) On triangulations of a\u00a0set of points in the\nplane. In: Proc. 18th IEEE Symp. on Foundations of Computer Science, pp\n228\u2013240","DOI":"10.1109\/SFCS.1977.21"},{"key":"475_CR57_475","unstructured":"McCabe P, Seidel R (2004) New lower bounds for the number of\nstraight-edge triangulations of a\u00a0planar point set. In: Proc. 20nd\nEuropean Workshop on Computational Geometry, pp 175\u2013176"},{"key":"475_CR58_475","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0020-0190(92)90129-J","volume":"42","author":"H Meijer","year":"1992","unstructured":"Meijer H, Rappaport D (1992) Computing the minimum weight\ntriangulation for a\u00a0set of linearly ordered points. Inf Process Lett 42:35\u201338","journal-title":"Inf Process Lett"},{"key":"475_CR59_475","unstructured":"Mulzer W, Rote G (2006) Minimum weight triangulation is\nNP-hard. In: Proc. 22nd Ann. ACM Symp. on Computational Geometry, pp 1\u201310"},{"key":"475_CR60_475","doi-asserted-by":"crossref","unstructured":"Musin OR (1997) Properties of the Delaunay triangulation.\nIn: Proc. 13th Ann. ACM Symp. on Computational Geometry, pp 424\u2013426","DOI":"10.1145\/262839.263061"},{"key":"475_CR61_475","doi-asserted-by":"crossref","unstructured":"Okabe A, Boots B, Sugihara K, Chiu SN (2000) \nSpatial Tesselations: Concepts and Applications of Voronoi Diagrams (2nd edn). \nWiley","DOI":"10.1002\/9780470317013"},{"key":"475_CR62_475","doi-asserted-by":"crossref","unstructured":"Ono T, Kyoda Y, Masade T, Hayase K, Shibuja T, Nakade M, Inabe\nM, Imai H, Imai K, Avis D (1996) A\u00a0package for triangulations.  In:\nProc. 12th. Ann. ACM Symp. on Computational Geometry, pp\nV17\u2013V18","DOI":"10.1145\/237218.237430"},{"key":"475_CR63_475","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/0196-6774(87)90020-4","volume":"8","author":"DA Plaisted","year":"1987","unstructured":"Plaisted DA, Hong J (1987) A\u00a0heuristic triangulation algorithm.\nJ\u00a0Algorithms 8:405\u2013437","journal-title":"J Algorithms"},{"key":"475_CR64_475","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02574375","volume":"12","author":"VT Rajan","year":"1994","unstructured":"Rajan VT (1994) Optimality of the Delaunay triangulation in\nRd. Discret Comput Geom 12:189\u2013202","journal-title":"Discret Comput Geom"},{"key":"475_CR65_475","doi-asserted-by":"crossref","unstructured":"Remy J, Steger A (2006) A\u00a0quasi-polynomial time approximation\nscheme for minimum weight triangulation. In: Proc. 38th ACM Symp. on Theory of\nComputing, pp 316\u2013325","DOI":"10.1145\/1132516.1132563"},{"key":"475_CR66_475","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/0167-8396(90)90011-F","volume":"7","author":"S Rippa","year":"1990","unstructured":"Rippa S (1990) Minimal roughness property of the Delaunay\ntriangulation. Comput Aided Geom Des 7:489\u2013497","journal-title":"Comput Aided Geom Des"},{"key":"475_CR67_475","doi-asserted-by":"crossref","unstructured":"Shamos MI,\nHoey D (1975) Closest point problems.  In: Proc. 16th IEEE Symp. on\nFoundations of Computer Science, pp\u00a0151\u2013162","DOI":"10.1109\/SFCS.1975.8"},{"key":"475_CR68_475","doi-asserted-by":"crossref","unstructured":"Sharir M, Welzl E (2006) Random triangulations of planar point\nsets. In: Proc. 22nd Ann. ACM Symposium on Computational Geometry, pp\n273\u2013281","DOI":"10.1145\/1137856.1137898"},{"key":"475_CR69_475","unstructured":"Snoeyink J\n\t  (1999) personal communication"},{"key":"475_CR70_475","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1093\/comjnl\/21.3.243","volume":"21","author":"R Sibson","year":"1978","unstructured":"Sibson R (1978) Locally equiangular triangulations. Comput J\n21:243\u2013245","journal-title":"Comput J"},{"key":"475_CR71_475","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/S0925-7721(96)00025-9","volume":"7","author":"P Su","year":"1995","unstructured":"Su\nP, Drysdale RLS (1995) A\u00a0comparison of sequential Delaunay triangulation\nalgorithms. Comput Geometr Theory Appl 7:361\u2013385","journal-title":"Comput Geometr Theory Appl"},{"key":"475_CR72_475","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1023\/A:1009796113861","volume":"1","author":"CA Wang","year":"1997","unstructured":"Wang CA, Chin F, Xu YF (1997) A\u00a0new subgraph of minimum weight\ntriangulations. J\u00a0Combin Optim 1:115\u2013127","journal-title":"J Combin Optim"},{"key":"475_CR73_475","unstructured":"Xu YF (1992) Minimum weight triangulation problem of a\u00a0planar\npoint set. Institute of Applied Mathematics, Academia Sinica, Beijing"},{"key":"475_CR74_475","first-page":"235","volume":"11B","author":"YF Xu","year":"1996","unstructured":"Xu YF (1996) On stable line segments in all triangulations.  Appl\nMath JCU 11B:235\u2013238","journal-title":"Appl Math JCU"},{"key":"475_CR75_475","unstructured":"Xu YF, Dai W (2005) An algorithm for generating a\u00a05-optimal\ntriangulation. In: Proc. China-Japan Joint Conference on Discrete Geometry,\nCombinatorics, and Graph Theory, Lecture Notes in Computer Science.\nSpringer"},{"key":"475_CR76_475","doi-asserted-by":"crossref","unstructured":"Yang BT, Xu YF, You ZY (1994) A\u00a0chain decomposition algorithm\nfor the proof of a\u00a0property on minimum weight triangulations.  In: Proc. 5th\nInt. Symp. on Algorithms and Computation (ISAAC), Lecture Notes in Computer\nScience, vol\u00a0834. Springer, pp 423\u2013427","DOI":"10.1007\/3-540-58325-4_207"}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T10:09:26Z","timestamp":1720692566000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":76,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_475","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}