Robust and Efﬁcient Delaunay triangulations of points on or close to a sphere

Manuel Caroli; Pedro M. M. De Castro; Sebastien Loriot; Monique Teillaud; Camille Wormser

inria-00405478, version 1

Robust and Efﬁcient Delaunay triangulations of points on or close to a sphere

Manuel Caroli () ¹, Pedro M. M. De Castro () ¹, Sebastien Loriot () ², Monique Teillaud () ¹, Camille Wormser ()^a^, 3

(2009)

Résumé : 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.

a – ETH Zurich
1 : GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
INRIA
2 : ABS (INRIA Sophia Antipolis)
INRIA
3 : Department of Computer Science (ETH Zurich)
ETH Zurich

inria-00405478, version 1
http://hal.inria.fr/inria-00405478
oai:hal.inria.fr:inria-00405478
Contributeur : Manuel Caroli <>
Soumis le : Lundi 20 Juillet 2009, 15:29:44
Dernière modification le : Mercredi 22 Juillet 2009, 15:38:56

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00405478"><monogr>
<author><persName><forename>Manuel</forename><surname>Caroli</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Saclay - Ile de France</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Pedro</forename><surname>M. M. De Castro</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Saclay - Ile de France</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Sebastien</forename><surname>Loriot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">ABS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Monique</forename><surname>Teillaud</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Saclay - Ile de France</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Camille</forename><surname>Wormser</surname></persName>
<affiliation>
<orgName type="laboratory">ETH Zurich</orgName>
<orgName type="team">Department of Computer Science</orgName>
<country>CH</country>
<orgName type="institution">ETH Zurich</orgName>
</affiliation>
</author>
<title type="main" level="m">Robust and Efﬁcient Delaunay triangulations of points on or close to a sphere</title><title type="main" level="m">Robust and Efﬁcient Delaunay triangulations of points on or close to a sphere</title><imprint><biblScope type="publicationDate">2009-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00405478</idno><idno type="HALFile">http://hal.inria.fr/inria-00405478/PDF/DT_sphere_RR.pdf</idno></biblStruct>
</listBibl>
</listBibl>