Computing Dirichlet tessellations†

Computing Dirichlet tessellations†

1981 | A. Bowyer
The paper by A. Bowyer presents an efficient algorithm for computing Dirichlet tessellations and Delaunay triangulations in \( k \)-dimensional Euclidean space (\( k \geq 2 \)). The algorithm is designed to be extendable to simpler non-Euclidean metric spaces. It has been implemented in ISO FORTRAN, and the execution times and stereoscopic images of the tessellation and triangulation are provided. In the introduction, the definitions of Dirichlet tessellations and Delaunay triangulations are explained, along with their properties and applications. The Dirichlet tessellation divides the plane into convex polygons based on the nearest neighbor rule, while the Delaunay triangulation connects points to form a triangulation of the convex hull. These structures have applications in various fields, including epidemic modeling, animal behavior analysis, spatial point process analysis, and surface fitting. The algorithm section details the data structure used to store the tessellation and triangulation, focusing on how to add a new point to the structure. The algorithm is designed to handle degeneracies, such as multiple points coinciding or lying in a hyperplane, by maintaining the validity of the structure and avoiding numerical issues. The implementation section discusses the programming details, including the use of ISO FORTRAN subroutines and the handling of floating-point calculations. The author's implementation successfully handles highly degenerate point patterns. Stereoscopic images of the tessellation and triangulation are also presented to visualize the structures. The references section lists key works that influenced the development of the algorithm.The paper by A. Bowyer presents an efficient algorithm for computing Dirichlet tessellations and Delaunay triangulations in \( k \)-dimensional Euclidean space (\( k \geq 2 \)). The algorithm is designed to be extendable to simpler non-Euclidean metric spaces. It has been implemented in ISO FORTRAN, and the execution times and stereoscopic images of the tessellation and triangulation are provided. In the introduction, the definitions of Dirichlet tessellations and Delaunay triangulations are explained, along with their properties and applications. The Dirichlet tessellation divides the plane into convex polygons based on the nearest neighbor rule, while the Delaunay triangulation connects points to form a triangulation of the convex hull. These structures have applications in various fields, including epidemic modeling, animal behavior analysis, spatial point process analysis, and surface fitting. The algorithm section details the data structure used to store the tessellation and triangulation, focusing on how to add a new point to the structure. The algorithm is designed to handle degeneracies, such as multiple points coinciding or lying in a hyperplane, by maintaining the validity of the structure and avoiding numerical issues. The implementation section discusses the programming details, including the use of ISO FORTRAN subroutines and the handling of floating-point calculations. The author's implementation successfully handles highly degenerate point patterns. Stereoscopic images of the tessellation and triangulation are also presented to visualize the structures. The references section lists key works that influenced the development of the algorithm.
Reach us at info@study.space