The Delaunay Tessellation (1928, 1934) (also known as Delaunay Triangulation) is a connection scheme based on triplets of points (in two dimensions). Three points (i, j, and k) are connected as a triangle if the circle which circumscribes them does not contain any other point l within its circumference. The Gabriel Graph is a subset of the Delaunay Tessellation.
Diagram demonstrating the Delaunay Tessellation.
For three-dimensional data points, the Delaunay tessellation is based on quadruplets of points, connected as tetrahedra rather than triangles (and is thus called a Delaunay tetrahedrization). Otherwise the logic is identical to the two-dimensional case.
The logical dual of the Delaunay tessellation is the Dirichlet Tessellation (1850). Dirichlet tessellations, more commonly known as Voronoi Polygons (1909) and Thiessen Polygons (1911) (among others), creates a cell around each point. The cell represents the area in space that is closer to that point than to any other point. The edges of each cell consist of the perpendicular bisectors of each connection in the Delaunay Tessellation.
Simple example of both Delaunay triangulation (red) and Dirichlet tessellation (blue) for 10 points; note that each blue line (sometimes if extended) is the perpendicular bisector of a red line.
The use of tessellations in statistical analysis is virtually an entire field to itself, with applications in a wide array of disciplines (Boots 1987; Okabe et al. 2000; Upton and Fingleton 1985). Analysis includes such characteristics as the calculation of the average size, number of sides, perimeter, etc., of each cell. While the Delaunay Tessellation can serve as a connection scheme, within PASSaGE the determination of the Dirichlet tessellation is currently used primarily for graphical output. Displaying a tessellation matrix in the output will include the area and perimeter of each internal polygon. Statistical analysis with the Dirichlet tessellation may be added in the future.
Example of a Delaunay triangulation (tessellation). Note that every internal “polygon”consists of a triangle.
Example of a Dirichlet tessellation. The area within each cell is closer to the point within the cell than any other point in the plot.