Research Interests & Publications



LNCS 1668 WAE 1999

An easy to use implementation of linear perturbations within CGAL

J. Comes and M. Ziegelmann


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.



Impressum & Webmaster     last change: 09.02.2011   mark.ziegelmanngmx.de