2 Question 2 -- Delaunay Triangulation

Delaunay triangulation is a method of constructing a surface mesh in a form suitable for computer graphics hardware. The input to the algorithm is a set of points in 2-Space (ie. a plane) and the height in 3-Space of the surface at that point. The output is connectivity information describing the surface as a series of tri-strips. In this way, it can be seen that Delaunay triangulation converts structured data (both regular and irregular) with implied connectivity to unstructured data with explicit connectivity.

Tri-strips are desirable from a computer graphics perspective because they are efficient in storage, (most) processing and importantly rendering. The essence is that after the first triangle has been specified, it only takes one vertex and two edges to extend the strip by another triangle. This leads to triangles requiring vertices and edges, both of which are more efficient than a triangular mesh of arbitrary connectivity. Further, for convenience the strips may be stored sequentially.

Delaunay triangulation works best when the surface has only small variations in the vertex density, that is, the vertices are evenly spaced in 3-Space. When this is the case, the algorithm will select triangles that are as close as possible to equilateral, resulting in an efficient and attractive surface. Further, the original data points are preserved, so no data is lost or approximated through interpolation.

However, the surface becomes more inefficient when it has large variations in the vertex density, that is, vertices which in some areas are closely bunched and in other areas are spread into vast plains. Here, the algorithm may potentially choose long, thin triangles in the regions of highly varying vertex density.

Delaunay triangulation cannot handle concave data sets at all. That is, where
the parallel projection of the surface onto a plane produces a concavity, the
Delaunay triangulation algorithm will blindly fill this cavity with triangles.
The algorithm can, however, produce concave surfaces, providing the above condition
is met^{2}.

The algorithm also suffers from being computationally slow to generate an optimal surface. This is usually avoided by allowing the surface to be ``close enough'', and applying heuristics to find semi-optimal surfaces.

In addition, data sets containing similar data points and features sometimes have dissimilar surfaces generated by Delaunay triangulation. A small change in a single vertex may alter the surrounding triangle or two, but this change may then have subsequent effects and repercussions throughout the rest of the surface. The two Delaunay meshes are still good approximations to the actual surfaces, but while the surfaces are similar the Delaunay meshes may not be (in terms of the triangles and their positions, sizes and relative layouts).

2000-08-22