Distributed {Voronoi} {Diagrams} and their applications in large-scale optimal transport

@inproceedings{levy_distributed_RM2024,
 abstract = {This inproceedings introduced Distributed Voronoi Diagrams, a set of algorithms that compute (generalized) Voronoi diagrams in parallel and in a distributed way. The main envisioned application is computing gigantic Voronoi (and Laguerre) diagrams, with billions cells on PC clusters, needed by some research in cosmology (reconstruction of the primordial Universe and simulation of models of gravity). First I make the simple observation that the cells defined by a subgraph of the Delaunay graph contain the Voronoi cells, and that one can deduce the missing edges from the intersections between those cells. Based on this observation, I introduce two algorithm, the Parallel Voronoi Diagram algorithm (PVD) that computes a Voronoi diagram in a shared memory machine, and the Distributed Voronoi Diagram algorithm (DVD) that can be used on a cluster and that exchanges vertices between the nodes as need be. I also report early experimental results, demonstrating that the DVD algorithm has the potential to solve some giga-scale semi-discrete optimal transport problems encountered in computational cosmology.},
 author = {Lévy, Bruno},
 booktitle = {Proc. 2024 RING Meeting},
 language = {en},
 pages = {22},
 publisher = {ASGA},
 title = {Distributed {Voronoi} {Diagrams} and their applications in large-scale optimal transport},
 year = {2024}
}