Exact arithmetic is used to build robust implementations of geometric
algorithms. However, it is slow, and computing to arbitrary precision is
unnecessary most of the time. Floating-point filters, which are commonly
used instead, are fast self-checking computations that fall back on exact
arithmetic when the check indicates that the fast calculation is incorrect.
The use of interval arithmetic in floating-point filters is attractive
because they can be used to build geometric software that does not assume
error-free inputs. However, the use of interval arithmetic might impose a
penalty on performance.
In this report, we study the performance impact of using interval arithmetic
based filters in the line-side and in-circle geometric predicates. We report
results obtained with implementations of two commonly used geometric
algorithms: Delaunay triangulation and convex hull computation, and for a
range of point distributions. Our results indicate that interval arithmetic
imposes a performance penalty of at most 2 in the worst case, and even
improves performance in some cases.