Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry

Abstract : We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be used to speed up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding modes of the widely used IEEE 754 standard. Using this approach we engineer an efficient floating-point filter for the computation of the sign of a determinant that works for arbitrary dimensions. We validate our approach experimentally, comparing it with other static, dynamic and semi-static filters.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2001, pp.25-47
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00344281
Contributeur : Sylvain Pion <>
Soumis le : jeudi 4 décembre 2008 - 13:44:57
Dernière modification le : samedi 27 janvier 2018 - 01:32:10
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:44:22

Fichier

interval_journal-1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00344281, version 1

Collections

Citation

Hervé Brönnimann, Christoph Burnikel, Sylvain Pion. Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry. Discrete Applied Mathematics, Elsevier, 2001, pp.25-47. 〈inria-00344281〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

268