A survey of algorithms for constructing a Delaunay triangulation

A large number of widely used algorithms for constructing a Delaunay triangulation are considered. A classification of these algorithms is proposed. Their performance evaluation is given for the average and worst cases. Some peculiarities of their realization are discussed. Four data structures for the representation of triangulation are analyzed. Several procedures for checking the Delaunay condition and for the triangulation merging are described.