A Fast Robust Algorithm for Computing Discrete Voronoi Diagrams

摘要

We describe an algorithm for the construction of discretized Voronoi diagrams on a CPU within the context of a large scale numerical fluid simulation.The Discrete Voronoi Chain (DVC) algorithm is fast, flexible and robust. Thealgorithm stores the Voronoi diagram on a grid or lattice that may be structuredor unstructured. The Voronoi diagram is computed by alternatively updating twolists of grid cells per particle to propagate a growth boundary of cells from theparticle locations. Distance tests only occur when growth boundaries from differentparticles collide with each other, hence the number of distance tests is effectivelyminimized. We give some empirical results for two and three dimensions. Themethod generalizes to any dimension in a straight forward manner. The distancetests can be based any metric.