Efficient Exact Geometric Predicates for Delaunay Triangulations

Olivier Devillers 1 Sylvain Pion 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates. Depending of what is called ``easy instances'', we usually classify filters as static or dynamic and also some in between categories often called semi-static. In this paper, we propose, in the context of three dimensional Delaunay triangulations: --- automatic tools for the writing of static and semi-static filters, --- a new semi-static level of filtering called translation filter, --- detailed benchmarks of the success rates of these filters and comparison with rounded arithmetic, long integer arithmetic and filters provided in Shewchuk's predicates. Our method is general and can be applied to all geometric predicates on points that can be expressed as signs of polynomial expressions. This work is applied in the CGAL library.
Type de document :
Communication dans un congrès
5th Workshop on Algorithm Engineering and Experiments (ALENEX), Jan 2003, Baltimore, Maryland, United States. pp.37-44, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00344517
Contributeur : Sylvain Pion <>
Soumis le : vendredi 5 décembre 2008 - 03:04:33
Dernière modification le : samedi 27 janvier 2018 - 01:31:48
Document(s) archivé(s) le : lundi 7 juin 2010 - 21:34:35

Fichier

alenex03.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00344517, version 1

Collections

Citation

Olivier Devillers, Sylvain Pion. Efficient Exact Geometric Predicates for Delaunay Triangulations. 5th Workshop on Algorithm Engineering and Experiments (ALENEX), Jan 2003, Baltimore, Maryland, United States. pp.37-44, 2003. 〈inria-00344517〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

287