One Sided Error Predicates in Geometric Computing
Lutz Kettner, Emo Welzl · 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 advanta...