Robust and Efficient Delaunay Triangulations of Points on or Close to a Sphere

Manuel Caroli, Pedro M. M. de Castro, Sébastien Loriot, Olivier Rouiller, Monique Teillaud, and Camille Wormser, “Robust and Efficient Delaunay Triangulations of Points on or Close to a Sphere,” in International Symposium on Experimental Algorithms (SEA), Springer Berlin Heidelberg, 2010, pp. 462–473. doi: 10.1007/978-3-642-13193-6_39.

We propose two ways to compute the Delaunay triangulation of points on a sphere, or of rounded points close to a sphere, both based on the classic incremental algorithm initially designed for the plane. We use the so-called space of circles as mathematical background for this work. We present a fully robust implementation built upon existing generic algorithms provided by the CGAL library. The efficiency of the implementation is established by benchmarks.

I did my internship at INRIA Sophia Antipolis in the Geometrica team under the supervision of Monique Teillaud while I was studying at École Centrale de Lille. I had the chance to work with the CGAL library. I worked on a prototype for a Delaunay triangulation on the sphere.