Delaunay Triangulation

it’s official for Wikipedia : divide and conquer algorithms are the faster for Delaunay triangulation ,so to celebrate let’s talk about this specific algorithm for the triangulation of a set of points (2D or 3D) which is called grid and is used in many aspects of scientific computing.

DELAUNΑY TRIANGULATION

DT combines several quality measures : maxmin angle condition,minmax constrained circumcenter etc .DT of a point set is the planar dual of the Voronoi diagram.The Voronoi Diagram is a partition of the plane into polygonal cells, each of one assinged to an initial point., so that the cell for input point P consists of a region fo the plane closer to P than any other input point.Any point (nodal-point of the grid) lies outside the circumcentre and hence any vertex of the Voronoi diagram has degree 3 and the DT will be a triangulation.

There are many algorythms for DT.Some of them have to do with the Convex hull of the set points.The main idea goes like this : Lift each point of the input to a paraboloid in one dimension up (for 2D it will be 3D) ,by mapping the point ,to the point .The convex hull of the lifted points can be divided  into lower and upper parts: a face belongs tho the lower convex hull if it is supported by a plane that separates the point set from .It can be shown that the DT of the input points is the projection of the lower convex hull onto the xy-plane:

Many algorythms of run-time are developed for DT.One nice one and pretty understanding is devide_and_conquer .For the generall overview of the most famous algorythms for DT and their run-time comparison is triangulation_algorythms_sigkrisi.

SOURCE CODE

you can try to compute the delauney triangulation from source code for your input data points from here (Fortran 90,C,C++)