2025/02/20 by Mizrachi, Maor, Raveh, Barak, Steinberg, Elad
#Computational Geometry (cs.CG) #Distributed #FOS: Computer and information sciences #FOS: Physical sciences #Instrumentation and Methods for Astrophysics (astro-ph.IM) #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2502.14825
Voronoi diagrams are essential geometrical structures with numerous applications, particularly astrophysics-driven finite volume methods. While serial algorithms for constructing these entities are well-established, parallel construction remains challenging. This is especially true in distributed memory systems, where each host manages only a subset of the input points. This process requires redistributing points across hosts and accurately computing the corresponding Voronoi cells. In this paper, we introduce a new distributed construction algorithm, which is implemented in our open-source C++ 3-dimensional Voronoi construction framework. Our approach leverages Delaunay triangulation as an intermediate step, which is then transformed into a Voronoi diagram. We introduce the algorithms we implemented for the precise construction and our load-balancing approach and compare the running time with other state-of-the-art frameworks. MadVoro is a versatile tool that can be applied in various scientific domains, such as mesh decomposition, computational physics, chemistry, and machine learning.