Exact Geometric Computation using Cascading

Christoph Burnikel, Stefan Funke, Michael Seel


In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision packages, we develop an easy-to-use expression compiler called EXPCOMP. EXPCOMP supports all common operations \( +,-,\cdot ,/,\sqrt{\,} \). Applying a new semi-static filter, EXPCOMP combines the speed of static filters with the power of dynamic filters. The filter stages deal with all kinds of floating-point exceptions, including underflow. The resulting programs show a very good runtime behaviour.

International Journal of Computational Geometry & Applications (IJCGA) , Vol. 11, No. 3 (2001) 245-266 (invited papers from SoCG 1998)

a preliminary version appeared in Proc. 14th ACM Symposium on Computational Geometry (SoCG) 1998, Minneapolis
PDF