HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Robust and Efficient Delaunay triangulations of points on or close to a sphere

Manuel Caroli 1 Pedro Machado Manhães de Castro 1 Sebastien Loriot 2 Olivier Rouiller 1 Monique Teillaud 1 Camille Wormser 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We propose two approaches for computing 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. The space of circles gives the mathematical background for this work. We implemented the two approaches in a fully robust way, building upon existing generic algorithms provided by the cgal library. The effciency and scalability of the method is shown by benchmarks.
Document type :
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

Contributor : Manuel Caroli Connect in order to contact the contributor
Submitted on : Thursday, December 17, 2009 - 4:29:52 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Saturday, November 26, 2016 - 3:20:55 PM


Files produced by the author(s)


  • HAL Id : inria-00405478, version 4



Manuel Caroli, Pedro Machado Manhães de Castro, Sebastien Loriot, Olivier Rouiller, Monique Teillaud, et al.. Robust and Efficient Delaunay triangulations of points on or close to a sphere. [Research Report] RR-7004, INRIA. 2009. ⟨inria-00405478v4⟩



Record views


Files downloads