A PROBABILISTIC ANALYSIS OF THE POWER OF ARITHMETIC FILTERS

The assumption of real-number arithmetic, which is at the basis of con ventional geometric algorithms, has been seriously challenged in recen t years, since digital computers do not exhibit such capability. A geo metric predicate usually consists of evaluating the sign of some algeb raic expression. In most cases, rounded computations yield a reliable result, but sometimes rounded arithmetic introduces errors which may i nvalidate the algorithms. The rounded arithmetic may produce an incorr ect result only if the exact absolute value of the algebraic expressio n is smaller than some (small) epsilon, which represents the largest e rror that may arise in the evaluation of the expression. The threshold epsilon 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 arithmetic filter. In thi s paper we develop a general technique for assessing the efficacy of a n arithmetic filter. The analysis consists of evaluating both the thre shold and the probability of failure of the filter. To exemplify the a pproach, 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 determinant s be no larger than some positive value V, with emphasis on small V, i s Theta(V) for the which-side predicate, while for the insphere predic ate it is Q(V-2/3) in dimension 1, O(V-1/2) in dimension 2, and O(V-1/ 2 In(1/V)) in higher dimensions. Constants are small, and are given in the paper.