Robust Construction of Voronoi Diagrams of Spherical Balls in Three-Dimensional Space. (November 2022)

• Record Type: Journal Article
• Authors: Lee, Mokwon; Sugihara, Kokichi; Kim, Deok-Soo
• Is Part Of: Computer aided design. Volume 152(2022)
• Publication Date: 2022-11
• Subjects: Topology-oriented incremental -- Additively weighted -- Spatial reasoning -- Tessellation -- Proximity -- Computational geometry; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103374
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Voronoi diagrams are useful for spatial reasoning among particles and there are many prior studies on their construction. However, most prior works were for the ordinary Voronoi diagrams of points in R 2 and R 3 . Here we propose a robust algorithm for constructing the Voronoi diagram of spherical balls in R 3, where the output is guaranteed to be at least topologically consistent. This topology-oriented incremental algorithm constructs the Voronoi diagram in O ( n 3 ) time in the worst case, whereas its empirical time behavior shows a strong linear fashion for all data we tested. The proposed algorithm is the three-dimensional generalization of its counterpart in the plane. It is implemented, thoroughly tested, and compared with two well-known programs. Current implementation processes approximately 350 balls per second using one core of ordinary desktop computer. This paper also contains an extensive review on the Voronoi diagrams of 2D circular disks and 3D spherical balls. We anticipate the algorithm will be widely used to solve application problems from many disciplines in science and engineering. The library is freely available from the github repository. Highlights: Topology-oriented incremental construction of the Voronoi diagram of 3D spheres. The first robust algorithm for constructing the Voronoi diagram of 3D spheres. Verification and validation through a complete implementation and experiment.