LNCS 1668 WAE 1999

An easy to use implementation of linear perturbations within CGAL

J. Comes and M. Ziegelmann
mark.ziegelmann@gmx.de

Abstract:

Most geometric algorithms are formulated under the non-degeneracy assumption which usually does not hold in practice. When implementing such an algorithm, a treatment of degenerate cases is necessary to prevent incorrect outputs or crashes. One way to overcome this nontrivial task is to use perturbations. In this paper we describe a generic implementation of efficient random linear perturbations within Cupgal and discuss the practicality of using it examining the convex hull problem, line segment intersection and Delaunay triangulation.