Some triangulations of a set of points ${\displaystyle {\mathcal {P}}\subset \mathbb {R} ^{d}}$  can be obtained by lifting the points of ${\displaystyle {\mathcal {P}}}$  into ${\displaystyle \mathbb {R} ^{d+1}}$  (which amounts to add a coordinate ${\displaystyle x_{d+1}}$  to each point of ${\displaystyle {\mathcal {P}}}$ ), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on ${\displaystyle \mathbb {R} ^{d}}$ . The triangulations built this way are referred to as the regular triangulations of ${\displaystyle {\mathcal {P}}}$ . When the points are lifted to the paraboloid of equation ${\displaystyle x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}}$ , this construction results in the Delaunay triangulation of ${\displaystyle {\mathcal {P}}}$ . Note that, in order for this construction to provide a triangulation, the lower convex hull of the lifted set of points needs to be simplicial. In the case of Delaunay triangulations, this amounts to require that no ${\displaystyle d+2}$  points of ${\displaystyle {\mathcal {P}}}$  lie in the same sphere.

Every triangulation of any set ${\displaystyle {\mathcal {P}}}$  of ${\displaystyle n}$  points in the plane has ${\displaystyle 2n-h-2}$  triangles and ${\displaystyle 3n-h-3}$  edges where ${\displaystyle h}$  is the number of points of ${\displaystyle {\mathcal {P}}}$  in the boundary of the convex hull of ${\displaystyle {\mathcal {P}}}$ . This follows from a straightforward Euler characteristic argument.^[5]

Triangle Splitting Algorithm : Find the convex hull of the point set ${\displaystyle {\mathcal {P}}}$  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.^[6]

Incremental Algorithm : Sort the points of ${\displaystyle {\mathcal {P}}}$  according to x-coordinates. The first three points determine a triangle. Consider the next point ${\displaystyle p}$  in the ordered set and connect it with all previously considered points ${\displaystyle \{p_{1},...,p_{k}\}}$  which are visible to p. Continue this process of adding one point of ${\displaystyle {\mathcal {P}}}$  at a time until all of ${\displaystyle {\mathcal {P}}}$  has been processed.^[7]

The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where ${\displaystyle n}$  is the number of points.

• Mesh generation
• Polygon triangulation