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

Manuel Caroli (1) , Pedro M M de Castro (1) , Sébastien Loriot (1) , Olivier Rouiller (1) , Monique Teillaud (1) , Camille Wormser (2)

1 GEOMETRICA - Geometric computing
2 ETH Zürich - Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]

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.

Domaines: Géométrie algorithmique [cs.CG]

Manuel Caroli, Pedro M M de Castro, Sébastien Loriot, Olivier Rouiller, Monique Teillaud, et al.. Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere. Symposium on Experimental Algorithms, 2010, Naples, Italy. pp.462-473. ⟨hal-03469649⟩