A Restricted Region of the Examination of Points for Checking the Circle Criterion

Abstract

In this paper, we present a sequential algorithm for constructing the Delaunay triangulation of a finite planar point set based on the divide-and-conquer strategy. In particular, we use a restricted region of the examination of points for checking the circle criterion. The efficiency of the proposed algorithm is verified by comparing its performance with the Delaunay triangulation implementation given by O’Rourke. The results show that the implementation of our algorithm significantly achieves better speedups than O’Rourke’s implementation