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.

10 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]