CMU-CS-00-172Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-00-172
December 2000
CMU-CS-00-172.ps
Keywords: Computational geometry, geometric predicates, geometric
robustness, interval arithmetic, error analysis
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 This page maintained by reports@cs.cmu.edu |