Improved initialisation for centroidal Voronoi tessellation and optimal Delaunay triangulation

Centroidal Voronoi tessellations and optimal Delaunay triangulations can be approximated efficiently by non-linear optimisation algorithms. This paper demonstrates that the point distribution used to initialise the optimisation algorithms is important. Compared to conventional random initialisation, certain low-discrepancy point distributions help convergence towards more spatially regular results and require fewer iterations for planar and volumetric tessellations.

Figure optionsDownload as PowerPoint slideHighlights
► CVT and ODT generation results depend on the initialisation of the optimisation algorithm.
► CVT and ODT results are significantly improved by low-discrepancy initialisation.
► Esp. the Hammersley sequence gives spatially very regular results within only a few iterations.