Computer Science Department
School of Computer Science, Carnegie Mellon University


A Performance Comparison of Interval Arithmetic and Error Analysis
in Geometric Predicates

Sanjit A. Seshia, Guy E. Blelloch, Robert W. Harper

December 2000

Keywords: Computational geometry, geometric predicates, geometric robustness, interval arithmetic, error analysis

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