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^2\) 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^2\) 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.