An international conference connecting people
in CAD research, education and business
Bookmark and Share
Copyright (C) CAD Solutions, LLC. All rights reserved.
Proceedings of CAD'16, 2016, 173-177
Voronoi Cells of Non-general Position Spheres using the GPU

Zhongyin Hu, Xiang Li, Sara McMains, University of California, Berkeley
Adarsh Krishnamurthy, Iowa State University
Iddo Hanniel, Technion, Israel Institute of Technology

Abstract. The Voronoi diagram is a fundamental construct in computational geometry, for which many algorithms have been proposed. However, Voronoi diagrams of large collections of higher order objects such as spheres in R3 have only been successfully computed by Kim et al., which is limited to input in general position. Our main contributions include: (1) A novel approach to compute Voronoi cells of spheres that exploits the parallelism of the GPU by shooting intersection rays and taking the lower envelope as points on Voronoi faces; (2) Separation of the construction of the topology of the Voronoi cells from the calculation of the geometry. The topology is calculated directly from the face sample points; (3) Accurate calculation of Voronoi vertices’ geometry by using the samples to initialize Newton-Raphson iteration; (4) Calculation of Voronoi cells of thousands of input spheres representing actual protein molecules can be generated by our algorithm. Our algorithm is robust even for spheres not in general position, handling Voronoi vertices with degree greater than four.

Keywords. Voronoi diagram, spheres, GPU, lower envelope 

DOI: 10.14733/cadconfP.2016.173-177