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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Jesper Jansson,
  • Christos Levcopoulos,
  • Andrzej Lingas,
  • Quan Xue

摘要

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.