Insert and delete algorithms for maintaining dynamic Delaunay triangulations

We recall that optimal condensing of nearest neighbor data requires the construction of the Delaunay triangulation of the training set. We argue that, from the viewpoint of computational complexity, an iterative approach using a dynamic triangulation is most desirable. We describe two algorithms, Insert and Delete, which permit to maintain a dynamic Delaunay triangulation.