Deterministic protocols for Voronoi diagrams and triangulations of planar point sets on the congested clique

We study the problems of computing the Voronoi diagram and a triangulation 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. First, we observe 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.). Next, 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 deterministically computed in O(log⁡n) rounds in this model. Finally, we present a deterministic O(log⁡n)-round protocol for a triangulation of n2 points with O(log⁡n)-bit coordinates in the Euclidean plane. It relies on our novel method for extending triangulations of two planar point sets separated by a straight line to a complete triangulation of the union of the sets in O(1) rounds.