An Experimental Analysis of Floating-Point Versus Exact Arithmetic
Martin Held, Willi Mann · 2011
In this paper we investigate how sophisticated floatingpoint codes that are in real-world use – VRONI for computing Voronoi diagrams, FIST for computing triangulations, and BONE for computing straight skeletons – can benefit from the use of the Core library (for exact geometric computing) or the MPFR library (for multiprecision arithmetic). We also discuss which changes to the codes were necessary in order to get them to run with these libraries. Furthermore, we compare our codes to codes provided by the CGAL project. By means of GMP-based (brute-force) verifiers we check the numerical validity of the outputs generated by all codes. As expected, the output precision of VRONI increases when MPFR is used, at a cost of an average slow-down by a multiplicative factor of 70. On the other hand, FIST demonstrates that a careful engineering can enable a code that uses floating-point arithmetic to run flawlessly, provided that the input coordinates are interpreted as genuine floating-point numbers. To our surprise, we could not get VRONI and BONE to work with CORE. It is similarly surprising that their CGAL counterparts did not fare well at all: we recorded drastically increased CPU-time consumptions combined with decreased accuracy of the numerical output. 1