Computing Dirichlet tessellations

Abstract

An efficient algorithm is proposed for computing the Dirichlet tessellation and Delaunay triangulation in a k dimensional Euclidean space (k≥2). The algorithm is designed in a way that should allow it to be extended to some of the simpler non-Euclidean metric spaces as well. The algorithm has been implemented in ISO FORTRAN by the author and execution time and stereoscopic pictures of the tessellation and triangulation are presented at the end of this paper.