Robust and efficient implementation of the Delaunay tree
Olivier Devillers, 06 - Valbonne (France). Unite de Recherche de Sophia-Antipolis Institut National de Recherche en Informatique et en Automatique (INRIA) · OpenGrey (Institut de l'Information Scientifique et Technique) · 1992
In this paper, we present some practical results concerning the implementation of the algorithm described in (DMT) which computes dynamically the Delaunay triangulation of a set of sites in the plane in logarithmic expected update time. More precisely, we show that the hypotheses of non degenerate positions can be dropped and the problem of precision can be treated correctly.