Improved Initialisation for Centroidal Voronoi Tessellation and Optimal Delaunay Triangulation

Authors: Jonathan Quinn, Feng Sun, Frank C Langbein, Yu-Kun Lai, Wenping Wang, Ralph R Martin

DOI: 10.1016/j.cad.2012.05.002

Abstract:

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.

Link to Paper

Authors

Dr Jonathan Quinn

Manifold sampling and low-discrepancy methods. Point based graphics and non-photorealistic rendering.

Dr Frank Langbein

Computational modelling and applied geometry for science and engineering applications.

Prof. Ralph Martin

Polygon mesh processing including registration, noise removal, segmentation and surface fitting.

Research Institute of Visual Computing