A SEQUENTIAL ALGORITHM FOR CONSTRUCTING THE DELAUNAY TRIANGULATION

Abstract

The problem of constructing Delaunay triangulation is one of the important problems in Computational Geometry. The Delaunay triangulation has been used widely in computational geometry and extended to other multi-purpose domains, for example, GIS, terrain modelling, computer graphics, pattern recognition, finite element analysis… As a result, developing fast and effective algorithms to construct the Delaunay triangulation is becoming more and more important. There are a variety of sequential algorithms implemented effectively for constructing the Delaunay triangulation. In this paper, we present a sequential algorithm for constructing the Delaunay triangulation of a finite planar point set based on divide-and-conquer stratery. In particular, we use a restricted area of the examination of points for testing the circle criterion. The efficiency of the proposed algorithm is verified by comparing its performance with the Delaunay triangulation procedure given by O’Rourke. The results show that the implementation of our algorithm significantly achieves better speedups over O’Rourke’s code.