8481 articles  [english version]

inria-00405478, version 3

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

Manuel Caroli () 1, Pedro M. M. De Castro () 1, Sebastien Loriot () 2, Monique Teillaud () 1, Camille Wormser () a, 3

N° RR-7004 (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
  • Domaine : Informatique/Géométrie algorithmique
  • Mots-clés : Computational Geometry – Delaunay Triangulation – Voronoi Diagram – Sphere – Space of Circles – Exact Geometric Computing – CGAL
  • Référence interne : RR-7004
  • Versions disponibles :  v1 (20-07-2009) v2 (27-07-2009) v3 (27-07-2009) v4 (17-12-2009)
 
  • inria-00405478, version 3
  • http://hal.inria.fr/inria-00405478
  • oai:hal.inria.fr:inria-00405478
  • Contributeur : Manuel Caroli <>
  • Soumis le : Lundi 27 Juillet 2009, 14:43:15
  • Dernière modification le : Lundi 27 Juillet 2009, 14:52:57