The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O(\log n)$ Deterministic Rounds on the Congested Clique
<|reference_start|>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.<|reference_end|>
@article{jansson2024the,
    title={The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O(\log n)$
  Deterministic Rounds on the Congested Clique},
    author={Jesper Jansson and Christos Levcopoulos and Andrzej Lingas},
    journal={arXiv preprint arXiv:2404.06068},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.06068},
    primaryClass={cs.CG cs.DS}
}