{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T22:48:07Z","timestamp":1778021287093,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642131929","type":"print"},{"value":"9783642131936","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13193-6_39","type":"book-chapter","created":{"date-parts":[[2010,4,27]],"date-time":"2010-04-27T07:54:59Z","timestamp":1272354899000},"page":"462-473","source":"Crossref","is-referenced-by-count":26,"title":["Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Caroli","sequence":"first","affiliation":[]},{"given":"Pedro M. M.","family":"de Castro","sequence":"additional","affiliation":[]},{"given":"S\u00e9bastien","family":"Loriot","sequence":"additional","affiliation":[]},{"given":"Olivier","family":"Rouiller","sequence":"additional","affiliation":[]},{"given":"Monique","family":"Teillaud","sequence":"additional","affiliation":[]},{"given":"Camille","family":"Wormser","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","unstructured":"Hull, a program for convex hulls, \n                    \n                      http:\/\/www.netlib.org\/voronoi\/hull.html"},{"key":"39_CR2","unstructured":"Qhull, \n                    \n                      http:\/\/www.qhull.org\/"},{"key":"39_CR3","unstructured":"Cgal, Computational Geometry Algorithms Library, \n                    \n                      http:\/\/www.cgal.org"},{"key":"39_CR4","unstructured":"Core number library, \n                    \n                      http:\/\/cs.nyu.edu\/exact\/core_pages"},{"key":"39_CR5","unstructured":"Leda, Library for efficient data types and algorithms, \n                    \n                      http:\/\/www.algorithmic-solutions.com\/enleda.htm"},{"key":"39_CR6","unstructured":"Three-dimensional convex hulls, \n                    \n                      http:\/\/www.simplex.t.u-tokyo.ac.jp\/~sugihara\/opensoft\/opensofte.html"},{"key":"39_CR7","unstructured":"IEEE standard for floating-point arithmetic. IEEE Std 754-2008, pp. 1\u201358 (August 2008)"},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/0216006","volume":"16","author":"F. Aurenhammer","year":"1987","unstructured":"Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM Journal of Computing\u00a016, 78\u201396 (1987)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"39_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams: A survey of a fundamental geometric data structure. ACM Computing Surveys\u00a023(3), 345\u2013405 (1991)","journal-title":"ACM Computing Surveys"},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-93816-3_9","volume-title":"Geometry","author":"M. Berger","year":"1987","unstructured":"Berger, M.: The space of spheres. In: Geometry, vol.\u00a01-2, pp. 349\u2013361. Springer, Heidelberg (1987)"},{"key":"39_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic Geometry","author":"J.D. Boissonnat","year":"1998","unstructured":"Boissonnat, J.D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, UK (1998); Translated by Herv\u00e9 Br\u00f6nnimann"},{"issue":"2","key":"39_CR12","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1093\/comjnl\/24.2.162","volume":"24","author":"A. Bowyer","year":"1981","unstructured":"Bowyer, A.: Computing Dirichlet tessellations. The Computer Journal\u00a024(2), 162\u2013166 (1981)","journal-title":"The Computer Journal"},{"key":"39_CR13","unstructured":"Brown, K.Q.: Geometric transforms for fast geometric algorithms. Ph.D. thesis, Dept. Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, Report CMU-CS-80-101 (1980)"},{"key":"39_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-04128-0_11","volume-title":"Algorithms - ESA 2009","author":"K. Buchin","year":"2009","unstructured":"Buchin, K.: Constructing Delaunay triangulations along space-filling curves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 119\u2013130. Springer, Heidelberg (2009)"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Caroli, M., Teillaud, M.: 3D periodic triangulations. In: CGALial Editorial Bard (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)","DOI":"10.1007\/978-3-642-04128-0_6"},{"key":"39_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-04128-0_6","volume-title":"Algorithms - ESA 2009","author":"M. Caroli","year":"2009","unstructured":"Caroli, M., Teillaud, M.: Computing 3D periodic triangulations. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 59\u201370. Springer, Heidelberg (2009); Full version available as INRIA Reserch Report No 6823, \n                    \n                      http:\/\/hal.inria.fr\/inria-00356871"},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Safe and effective determinant evaluation. In: Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science, October 1992, pp. 387\u2013395 (1992)","DOI":"10.1109\/SFCS.1992.267751"},{"issue":"4","key":"39_CR18","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"K.L. Clarkson","year":"1993","unstructured":"Clarkson, K.L., Mehlhorn, K., Seidel, R.: Four results on randomized incremental constructions. Computational Geometry: Theory and Applications\u00a03(4), 185\u2013212 (1993)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"39_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.2307\/2303924","volume":"50","author":"H.S.M. Coxeter","year":"1943","unstructured":"Coxeter, H.S.M.: A geometrical background for de Sitter\u2019s world. American Mathematical Monthly\u00a050, 217\u2013228 (1943)","journal-title":"American Mathematical Monthly"},{"key":"39_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000)","edition":"2"},{"key":"39_CR21","unstructured":"de Castro, P.M.M., Cazals, F., Loriot, S., Teillaud, M.: 3D spherical geometry kernel. In: CGAL User and Reference Manual. CGAL Editorial Board, 3.5 edn. (2009)"},{"issue":"6-7","key":"39_CR22","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1016\/j.comgeo.2008.10.003","volume":"42","author":"P.M.M. Castro de","year":"2009","unstructured":"de Castro, P.M.M., Cazals, F., Loriot, S., Teillaud, M.: Design of the CGAL 3D Spherical Kernel and application to arrangements of circles on a sphere. Computational Geometry: Theory and Applications\u00a042(6-7), 536\u2013550 (2009)","journal-title":"Computational Geometry : Theory and Applications"},{"key":"39_CR23","unstructured":"Delage, C.: Spatial sorting. In: CGAL Editorial Board (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)"},{"key":"#cr-split#-39_CR24.1","unstructured":"Devillers, O., Meiser, S., Teillaud, M.: The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. In: Proceedings 4th Canadian Conference on Computational Geometry, pp. 263-268 (1992)"},{"key":"#cr-split#-39_CR24.2","unstructured":"Full version available as INRIA Research Report No 1620,     http:\/\/hal.inria.fr\/inria-00074941"},{"key":"39_CR25","unstructured":"Fogel, E., Setter, O.: Software for Voronoi diagram on a sphere. Personal communication"},{"key":"39_CR26","doi-asserted-by":"crossref","unstructured":"Fogel, E., Setter, O., Halperin, D.: Exact implementation of arrangements of geodesic arcs on the sphere with applications. In: Abstracts of 24th European Workshop on Computational Geometry, pp. 83\u201386 (2008)","DOI":"10.1145\/1377676.1377711"},{"issue":"1","key":"39_CR27","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/103162.103163","volume":"23","author":"D. Goldberg","year":"1991","unstructured":"Goldberg, D.: What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys\u00a023(1), 5\u201348 (1991)","journal-title":"ACM Computing Surveys"},{"key":"39_CR28","unstructured":"Hert, S., Schirra, S.: 3D convex hulls. In: CGAL Editorial Board (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)"},{"key":"39_CR29","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.comgeo.2007.06.003","volume":"40","author":"L. Kettner","year":"2008","unstructured":"Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., Yap, C.: Classroom examples of robustness problems in geometric computations. Computational Geometry: Theory and Applications\u00a040, 61\u201378 (2008)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"39_CR30","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/B978-0-12-587260-7.50011-X","volume-title":"Math. Software III","author":"C.L. Lawson","year":"1977","unstructured":"Lawson, C.L.: Software for C\n                  1 surface interpolation. In: Rice, J.R. (ed.) Math. Software III, pp. 161\u2013194. Academic Press, New York (1977)"},{"issue":"1","key":"39_CR31","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jlap.2004.07.006","volume":"64","author":"C. Li","year":"2005","unstructured":"Li, C., Pion, S., Yap, C.K.: Recent progress in exact geometric computation. Journal of Logic and Algebraic Programming\u00a064(1), 85\u2013111 (2005)","journal-title":"Journal of Logic and Algebraic Programming"},{"key":"39_CR32","unstructured":"Muller, J.M.: On the definition of \n                    \n                      \n                    \n                    $\\mbox{ulp}(x)$\n                  . Research Report 5504, INRIA (February 2005), \n                    \n                      http:\/\/hal.inria.fr\/inria-00070503\/"},{"key":"39_CR33","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0925-7721(02)00077-9","volume":"23","author":"H.S. Na","year":"2002","unstructured":"Na, H.S., Lee, C.N., Cheong, O.: Voronoi diagrams on the sphere. Computational Geometry: Theory and Applications\u00a023, 183\u2013194 (2002)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"39_CR34","unstructured":"Pion, S., Teillaud, M.: 3D triangulation data structure. In: CGAL Editorial Board (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)"},{"key":"39_CR35","unstructured":"Pion, S., Teillaud, M.: 3D triangulations. In: CGAL Editorial Board (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)"},{"key":"39_CR36","unstructured":"Pion, S., Yvinec, M.: 2D triangulation data structure. In: CGAL Editorial Board (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)"},{"issue":"3","key":"39_CR37","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1145\/275323.275329","volume":"23","author":"R.J. Renka","year":"1997","unstructured":"Renka, R.J.: Algorithm 772: STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere. ACM Transactions on Mathematical Software\u00a023(3), 416\u2013434 (1997), Software available at \n                    \n                      http:\/\/orion.math.iastate.edu\/burkardt\/f_src\/stripack\/stripack.html","journal-title":"ACM Transactions on Mathematical Software"},{"issue":"1","key":"39_CR38","first-page":"69","volume":"6","author":"K. Sugihara","year":"2002","unstructured":"Sugihara, K.: Laguerre Voronoi diagram on the sphere. Journal for Geometry and Graphics\u00a06(1), 69\u201381 (2002)","journal-title":"Journal for Geometry and Graphics"},{"key":"39_CR39","series-title":"Lecture Notes Series on Computing","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1142\/9789812831699_0011","volume-title":"Computing in Euclidean Geometry","author":"C.K. Yap","year":"1995","unstructured":"Yap, C.K., Dub\u00e9, T.: The exact computation paradigm. In: Du, D.-Z., Hwang, F.K. (eds.) Computing in Euclidean Geometry, 2nd edn. Lecture Notes Series on Computing, vol.\u00a04, pp. 452\u2013492. World Scientific, Singapore (1995)","edition":"2"},{"key":"39_CR40","unstructured":"Yvinec, M.: 2D triangulations. In: CGAL Editorial Board (ed.) CGAL User and Reference Manual, 3.5 edn. (2009)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13193-6_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T14:31:19Z","timestamp":1558276279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13193-6_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642131929","9783642131936"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13193-6_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}