Zusammenfassung Voronoi-Diagramme sind wesentliche geometrische Strukturen mit zahlreichen Anwendungen, insbesondere in von der Astrophysik motivierten Finite-Volumen-Methoden. Während serielle Algorithmen zur Konstruktion dieser Entitäten gut etabliert sind, bleibt die parallele Konstruktion eine Herausforderung. Dies gilt insbesondere in verteilten Speichersystemen, in denen jeder Host nur eine Teilmenge der Eingabepunkte verwaltet. Dieser Prozess erfordert eine Neuzuordnung von Punkten über Hosts hinweg und die genaue Berechnung der entsprechenden Voronoi-Zellen. In diesem Papier stellen wir einen neuen verteilten Konstruktionsalgorithmus vor, der in unserem Open-Source C++ 3-dimensionalen Voronoi-Konstruktionsrahmen implementiert ist. Unser Ansatz nutzt die Delaunay-Triangulation als Zwischenschritt, der dann in ein Voronoi-Diagramm umgewandelt wird. Wir stellen die Algorithmen vor, die wir für die präzise Konstruktion und unseren Lastenausgleichsansatz implementiert haben, und vergleichen die Laufzeit mit anderen state-of-the-art Rahmenbedingungen. MadVoro ist ein vielseitiges Werkzeug, das in verschiedenen wissenschaftlichen Bereichen wie der Maschenzerlegung, der computergestützten Physik, der Chemie und dem maschinellen Lernen angewendet werden kann.
Mizrachi et al. (Tue,) untersuchten diese Frage.