Fast capacity constrained Voronoi tessellation
Hongwei Li, Diego Nehab, Li‐Yi Wei, Pedro V. Sander, Chi‐Wing Fu · 2010
Capacity constrained Voronoi tessellation (CCVT) [Balzer et al. 2009] addresses a crucial quality issue of Lloyd relaxation but at the expense of slower computation, which could hinder its potential wide adoption. We present a fast capacity constrained Voronoi tessellation algorithm which is orders of magnitude faster than the original method proposed by Balzer et al. [2009] (and 10x faster than a previous accelerated implementation of the same technique) while maintaining excellent distribution quality and scaling very well as the number of points increase.