Two Algorithms for Constructing a Delaunay Triangulation
Lee D.T. and B.J. Schacter
International Journal of Computer and Information Sciences, Plenum Press, Vol 3, Num 9, 1980
This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set of N points. The first algorithm uses a divide and conquer approach. It runs in O(N log N) time, which is assymtotically optimal. The second algorithm is iterative and requires O(N^2) time in the worst case. However, its average case performance is comparable to that of the first algorithm.
Contact author(s) or publisher for availability and copyright information on above referenced article