Premium
Fast and robust Delaunay tessellation in periodic domains
Author(s) -
Thompson Karsten E.
Publication year - 2002
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.558
Subject(s) - tessellation (computer graphics) , delaunay triangulation , voronoi diagram , computation , context (archaeology) , convex hull , point (geometry) , regular polygon , algorithm , chew's second algorithm , mathematics , scaling , ruppert's algorithm , tetrahedron , computer science , mathematical optimization , bowyer–watson algorithm , geometry , paleontology , biology
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 10 5 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 © 2002 John Wiley & Sons, Ltd.