One Sided Error Predicates in Geometric Computing. Lutz Kettner and Emo Welzl. In: Kurt Mehlhorn (Eds.), Proc. 15th IFIP World Computer Congress, Fundamentals - Foundations of Computer Science, pp. 13-26, August 1998.
A conservative implementation of a predicate returns true only if the exact predicate is true. That is, we accept a one sided error for the implementation. For geometric predicates, such as orientation- or incircle-tests, this allows efficient floating point implementations of the predicates with rare occurrences of the one sided error.
We discuss the use of such conservative implementations for convex hull and triangulation algorithms for point sets in the plane. The resulting programs show a minor slowdown compared to an implementation that completely ignores the finite precision issue. However, our programs always produce output that satisfies basic desirable properties. The output can be easily checked for correctness and - if necessary - it can be repaired with an exact implementation of the needed predicates.
Although (or since?) conservative implementations of predicates cannot detect degeneracies, the programs work for degenerate input. In fact, in our experiments the advantage in running time compared to exact implementations of predicates (based on floating point filters) was most apparent for highly degenerate inputs.