This paper by D. T. Lee and B. J. Schachter provides a comprehensive discussion of the Delaunay triangulation, reviewing its geometric properties and applications. The authors present two algorithms for constructing the triangulation over a set of \( N \) points in the plane. The first algorithm employs a divide-and-conquer approach, achieving an asymptotically optimal time complexity of \( O(N \log N) \). The second algorithm is iterative and has a worst-case time complexity of \( O(N^2) \), but its average-case performance is comparable to the first algorithm. The paper also delves into the definition and properties of the Delaunay triangulation, emphasizing its use in fitting triangular faceted surfaces to digital terrain data, particularly for visual flight simulators.This paper by D. T. Lee and B. J. Schachter provides a comprehensive discussion of the Delaunay triangulation, reviewing its geometric properties and applications. The authors present two algorithms for constructing the triangulation over a set of \( N \) points in the plane. The first algorithm employs a divide-and-conquer approach, achieving an asymptotically optimal time complexity of \( O(N \log N) \). The second algorithm is iterative and has a worst-case time complexity of \( O(N^2) \), but its average-case performance is comparable to the first algorithm. The paper also delves into the definition and properties of the Delaunay triangulation, emphasizing its use in fitting triangular faceted surfaces to digital terrain data, particularly for visual flight simulators.