The Voronoi Diagram of Weakly Smooth Planar Point Sets in O (n) Deterministic Rounds on the Congested Clique

We study the problem of computing the Voronoi diagram of a set of n² points with O (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 n² points with O (n) -bit coordinates in the unit square then the Voronoi diagram of the point set within the unit square can be computed in O (n) rounds in this model.