triangulations in the plane Triangle Splitting Algorithm : Find the convex hull of the point set and triangulate this hull as a polygon. Choose an interior point and draw edges to the three vertices of the triangle that contains it. Continue this process until all interior points are exhausted. Incremental Algorithm : Sort the points of according to x-coordinates. The first three points determine a triangle. Consider the next point in the ordered set and connect it with all previously considered points which are visible to p. Continue this process of adding one point of at a time until all of has been processed. Time complexity of various algorithms The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where is the number of points. See also Mesh generation Polygon triangulation Notes References Triangulation (geometry) de:Gitter (Geometrie)#Dreiecksgitter