s'authentifier
version française rss feed

inria-00071232, version 1

Formally certified floating-point filters for homogeneous geometric predicates

Guillaume Melquiond () 1, Sylvain 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.

  • 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
  • oai:hal.inria.fr:inria-00071232
  • Contributeur : 
  • Soumis le : Mardi 23 Mai 2006, 14:44:43
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:25
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...