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

We study the problem of computing the Voronoi diagram of a set of n² 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 n² 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.