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.

翻译：Voronoi图是关键的几何结构，在众多领域具有广泛应用，特别是在天体物理驱动的有限体积方法中。虽然构建这些实体的串行算法已较为成熟，但并行构建仍面临挑战。这在分布式内存系统中尤为突出，其中每个主机仅管理输入点集的一个子集。该过程需要在主机间重新分配点，并精确计算相应的Voronoi单元。本文提出一种新的分布式构建算法，并在我们开源的C++三维Voronoi构建框架中实现。我们的方法以Delaunay三角剖分为中间步骤，再将其转换为Voronoi图。我们介绍了为实现精确构建所实现的算法及负载均衡策略，并将运行时间与其他先进框架进行了对比。MadVoro是一个多功能工具，可应用于网格分解、计算物理、化学和机器学习等多种科学领域。