MadVoro: Parallel Construction of Voronoi Diagrams in Distributed Memory Systems
Maor Mizrachi and Barak Raveh and Elad Steinberg
Voronoi图是必不可少的几何结构,具有许多应用,特别是天体物理学驱动的有限体积方法。 虽然构建这些实体的串行算法是完善的,但并行构建仍然具有挑战性。 在分布式内存系统中尤其如此,每个主机只管理输入点的一个子集。 这个过程需要跨主机重新分配点,并准确计算相应的Voronoi单元。 在本文中,我们引入了一种新的分布式构建算法,该算法在我们的开源C++三维Voronoi构建框架中实现。 我们的方法利用Delaunay三角测量作为中间步骤,然后将其转化为Voronoi图。 我们介绍了我们为精确构造和负载平衡方法实现的算法,并将运行时间与其他最先进的框架进行比较。 MadVoro是一种多功能工具,可以应用于各种科学领域,如网格分解,计算物理,化学和机器学习。
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 pape...
