Authors
Yanyang Xiao, Juan Cao, Zhonggui Chen
Published in
IEEE transactions on visualization and computer graphics. Volume PP. Oct 12, 2026. Epub Oct 12, 2026.
Abstract
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.
PMID:
42862604
Bibliographic data and abstract were imported from PubMed on 13 Oct 2026.
Read full publication at:
Please sign in
to see all details.
Advertisement
Stats
- Recommendations n/a n/a positive of 0 vote(s)
- Views 8
- Comments 0