A Lazy Object-Oriented Kernel for Geometric Computation

Stefan Funke, Kurt Mehlhorn


In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the exact number types provided by LEDA allowing for efficient and exact computation with rational and algebraic geometric objects.

It is the first kernel design which uses floating-point filter techniques on the level of geometric constructions. The experiments we present -- partly using the CGAL framework -- show a great improvement in speed and -- maybe even more important for practical applications -- memory consumption when dealing with more complex geometric computations.


Computational Geometry - Theory and Applications (CGTA), Vol. 22, Issue 1-3, May 2002, p. 99-118 (invited papers from SoCG 2000)


a preliminary version appeared in Proc. 16th ACM Symposium on Computational Geometry (SoCG) 2000, Hong Kong
PDF