Fast and robust Delaunay tessellation in periodic domains

An algorithm is presented for constructing three-dimensional Delaunay tessellations in periodic domains. Applications include mesh generation for periodic transport problems and geometric decomposition for modelling particulate structures. The algorithm is a point insertion technique, and although the general framework is similar to point insertion in a convex hull, a number of new issues are introduced by periodicity. These issues are discussed in detail in the context of the computational algorithm. Examples are given for the tessellation of random points and random sphere packings. Performance data for the algorithm are also presented. These data show an empirical scaling of the computation time with size of O(N-1.11) and tessellation rates of 7000-14000 tetrahedrons per second for the problems studied (up to 101 points). A breakdown of the performance is given, which shows the computational load is shared most heavily by two specific parts of the point-insertion procedure. Copyright (C) 2002 John Wiley Sons, Ltd.