2024/04/09 by Jesper Jansson, Jansson, Jesper, Christos Levcopoulos +3
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Mathematics and Applications #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2404.06068
openalex publication_date 2024/04/09 · openalex created_date 2024/04/12 · openalex updated_date 2026/07/28
We study the problem of computing the Voronoi diagram of a set of n2 points with O(log n)-bit coordinates in the Euclidean plane in a substantially sublinear in n number of rounds in the congested clique model with n nodes. Recently, Jansson et al. have shown that if the points are uniformly at random distributed in a unit square then their Voronoi diagram within the square can be computed in O(1) rounds with high probability (w.h.p.). We show that if a very weak smoothness condition is satisfied by an input set of n2 points with O(log n)-bit coordinates in the unit square then the Voronoi diagram of the point set within the unit square can be computed in O(log n) rounds in this model.