Interval arithmetic yields efficient dynamic filters for computational geometry

We discuss floating-point filters as a means of restricting the precision n eeded fur 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 interva l arithmetic that is strongly influenced by the rounding modes of the widel y used IEEE Standard 754. Using this approach we engineer an efficient floa ting-point filter for the computation of the sign of a determinant that wor ks for arbitrary dimensions, We validate our approach experimentally, compa ring it with other static, dynamic and semi-static filters. (C) 2001 Elsevi er Science B.V. All rights reserved.