inria-00071232, version 1
Formally certified floating-point filters for homogeneous geometric predicates
Guillaume Melquiond
1Sylvain Pion
2
N° RR-5644 (2005)
Résumé : Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where floating-point computations could lead to wrong results. Taking into account all the potential problems is a tedious work to do by hand. We study in this paper a floating-point implementation of a filter for the orientation-2 predicate, and how a formal and partially automatized verification of this algorithm avoided many pitfalls. The presented method is not limited to this particular predicate, it can easily be used to produce correct semi-static floating-point filters for other geometric predicates.
- 1 : GEOMETRICA (INRIA Sophia Antipolis)
- INRIA
- 2 : ARENAIRE (Inria Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
- INRIA – CNRS : UMR5668 – Université Claude Bernard - Lyon I – École Normale Supérieure - Lyon
- Domaine : Informatique/Autre
- Mots-clés : GEOMETRIC PREDICATES / SEMI-STATIC FILTERS / FORMAL PROOFS / FLOATING-POINT
- Référence interne : RR-5644
- inria-00071232, version 1
- http://hal.inria.fr/inria-00071232
- oai:hal.inria.fr:inria-00071232
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mardi 23 Mai 2006, 14:44:43
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:25






Documents associés

Exporter