Delaunay triangulations of closed Euclidean \(d\)-orbifolds (Q309648)

The main result of this paper gives an algorithm, in the spirit of extending the standard incremental algorithm [\textit{A. Bowyer}, ``Computing Dirichlet tessellations'', Comput. J. 24, 162--166 (1981; \url{doi:10.1093/comjnl/24.2.162})] for computing the Delaunay triangulation of a point set in \(\mathbb{E}^{n}\), for computing the Delaunay triangulation of a point set for a closed (compact) Euclidean \(n\)-manifold or \(n\)-orbifold. The latter is defined in this paper as the projection of an appropriate triangulation of the universal cover \(\mathbb{E}^{n}\). The authors give a simple geometric condition for checking whether a partition of such a manifold forms a triangulation, and develop an incremental algorithm that computes either the Delaunay triangulation or, if this does not exist, then the Delauney triangulation of a finite-sheeted covering space. The paper concludes with an extensive study of the 3D flat torus, complete with experimental observations featuring a software package of the authors which has already been used by cosmologists and researchers in other disciplines.