A Probabilistic Analysis of the Power of Arithmetic Filters

Olivier Devillers 1 Franco Preparata
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such capability. A geometric predicate usually consists of evaluating the sign of some algebraic expression. In most cases, rounded computations yield a reliable result, but sometimes rounded arithmetic introduces errors which may invalidate the algorithms. The rounded arithmetic may produce an incorrect result only if the exact absolute value of the algebraic expression is smaller than some (small) $\varepsilon$, which represents the largest error that may arise in the evaluation of the expression. The threshold $\varepsilon$ depends on the structure of the expression and on the adopted computer arithmetic, assuming that the input operands are error-free. A pair (arithmetic engine,threshold) is an {\em arithmetic filter}. In this paper we develop a general technique for assessing the efficacy of an arithmetic filter. The analysis consists of evaluating both the threshold and the probability of failure of the filter. To exemplify the approach, under the assumption that the input points be chosen randomly in a unit ball or unit cube with uniform density, we analyze the two important predicates "which-side» and 'insphere». We show that the probability that the absolute values of the corresponding determinants be no larger than some positive value $V$, with emphasis on small $V$, is $\Theta(V)$ for the which-side predicate, while for the insphere predicate it is $\Theta(V^{\frac{2}{3}})$ in dimensiona- 1, $O(V^{\frac{1}{2}})$ in dimension 2, and $O(V^{\frac{1}{2}}\ln \frac{1}{V})$ in higher dimensions. Constants are small, and are given in the paper.
Type de document :
Rapport
RR-2971, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073727
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:36:59
Dernière modification le : samedi 27 janvier 2018 - 01:31:29
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:06:20

Fichiers

Identifiants

  • HAL Id : inria-00073727, version 1

Collections

Citation

Olivier Devillers, Franco Preparata. A Probabilistic Analysis of the Power of Arithmetic Filters. RR-2971, INRIA. 1996. 〈inria-00073727〉

Partager

Métriques

Consultations de la notice

278

Téléchargements de fichiers

87