One Sided Error Predicates in Geometric Computing

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.

Joint work with Emo Welzl.