Vertex removal in two-dimensional Delaunay triangulation: Speed-up by low degrees optimization

The theoretical complexity of vertex removal in a Delaunay triangulation is often given in terms of the degree d of the removed point, with usual results O(d), , or O(d2). In fact, the asymptotic complexity is of poor interest since d is usually quite small. In this paper we carefully design code for small degrees 3⩽d⩽7, it improves the global behavior of the removal for random points by more than 45%.