A Hybridized Method for Building Delaunay Triangulation
一种生成Delaunay三角网的合成算法

A wide variety of algorithms have been proposed to construct triangulation. They fall into three broad categories: divide\|and\|conquer, incremental insertion and triangulation growth. The first two groups of the methods have been extensively applied to many disciplines because of their easiness in implementation. They are, however, constrained either by their computational inefficiency or by their stringent demand on computer memory. In this paper a hybridized method is proposed to take advantage of both algorithms' strengths so that these limitations could be overcome. In a test of 2533 points, the computation efficiency of the hybridized method is much higher than that of incremental insertion method in all cases, and is also higher than that of divide\|and\|conquer method in most cases. The best efficiency is achieved when the data points are partitioned into one\|tenth of the original size.