A certified conflict locator for the incremental maintenance of the Delaunay graph of semi-algebraic sets

Abstract

Most of the curves and surfaces encountered in geometric modelling are defined as the set of solutions of a system of algebraic equations or inequalities (semi-algebraic sets). The Voronoi diagram of a set of sites is a decomposition of the space into proximal regions (one for each site). Voronoi diagrams have been used to answer proximity queries. The dual graph of the Voronoi diagram is called the Delaunay graph. Only approximations by conics can guarantee a proper continuity of the first order derivative at contact points, which is necessary for guaranteeing the exactness of the Delaunay graph. The central idea of this paper is that a (one time) symbolic preprocessing may accelerate the certified numerical evaluation of the Delaunay graph conflict locator. The symbolic preprocessing is the computation of the implicit equation of the generalised offset to conics. The certified computation of the Delaunay graph conflict locator relies on theorems on the uniqueness of a root in given intervals (Kantorovich, Moore-Krawczyk). For conics, the computations get much faster by considering only the implicit equations of the generalised offsets.