Efficient Computation of Restricted Voronoi Diagrams Using Point-in-Cell Tests

We present a novel and efficient method for computing restricted Voronoi diagrams-that is, Voronoi diagrams constrained by a given domain. The intersection of the domain with a Voronoi cell (domain-cell intersection) is obtained by successively clipping the domain against the cell boundaries. Unlike existing approaches, we introduce an edge-based search scheme to identify the clipping planes (bisectors). A point-in-cell test is first employed to determine whether a spatial point lies inside a target Voronoi cell. Subsequently, for each edge of the intermediate domain-cell intersection, a clipping operation is performed only when its two endpoints lie inside and outside the corresponding Voronoi cell, respectively, and the required bisector can be found via a few point-in-cell tests. Consequently, our method performs exclusively the clippings that contribute to the final result, offering a substantial advantage over state-of-the-art approaches. Furthermore, since each domain-cell intersection can be computed independently, we extend our method to GPUs for parallel Voronoi diagram computation. Experimental results demonstrate that our method consistently outperforms state-of-the-art approaches, irrespective of the site distribution.