MadVoro: Parallel Construction of Voronoi Diagrams in Distributed Memory Systems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911248338124800 |
|---|---|
| author | Mizrachi, Maor Raveh, Barak Steinberg, Elad |
| author_facet | Mizrachi, Maor Raveh, Barak Steinberg, Elad |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14825 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | MadVoro: Parallel Construction of Voronoi Diagrams in Distributed Memory Systems Mizrachi, Maor Raveh, Barak Steinberg, Elad Instrumentation and Methods for Astrophysics Computational Geometry Distributed, Parallel, and Cluster Computing 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. |
| title | MadVoro: Parallel Construction of Voronoi Diagrams in Distributed Memory Systems |
| topic | Instrumentation and Methods for Astrophysics Computational Geometry Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2502.14825 |