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
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.