A faster circle-sweep Delaunay triangulation algorithm

This paper presents a new way to compute the Delaunay triangulation of a planar set P of n points, using sweep-circle technique combined with the standard recursive edge-flipping. The algorithm sweeps the plane by an increasing circle whose center is a fixed point in the convex hull of P. Empirical results and comparisons show that it reduces the number of in-circle tests and edge-flips, and it is efficient in practice.

► We presented a sweep-circle algorithm to compute the Delaunay triangulation (DT). ► The circle sweeps the plane and forms new triangles by recursive edge-flipping. ► This algorithm reduces the number of in-circle tests and edge-flips. ► It is the fastest, in comparison with other DT algorithms.