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

Abstract

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.

12 pages, 3 figures