Fast Construction Method for Restricted Voronoi Diagrams Driven by Four Nearest Neighbors

Restricted Voronoi diagrams are widely used in fields such as computer graphics, and improving their construction efficiency is important for downstream applications. Addressing the issue in mainstream methods where partial clippings contribute nothing to the final result, this paper proposes a fast construction method driven by four-nearest-neighbor searches. It iteratively searches for Voronoi cell-mesh face pairs via propagation and sequentially computes their intersections. The core innovation lies in the efficient computation of intersections between Voronoi cells and mesh faces. For each edge of a face, if its two endpoints belong to different Voronoi cells, a bisector between the target site and one of its neighbors is found through several four-nearest-neighbor searches and used to clip the face. Comparative experiments with mainstream methods demonstrate that the proposed method achieves higher efficiency and exhibits significantly reduced sensitivity to site distribution. In tests with 50k sites and 50k mesh faces under random site distribution, the proposed method reduced computation time by 71% and 30% respectively compared to the two mainstream approaches.