Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Jansson, Jesper ; Levcopoulos, Christos LU orcid ; Lingas, Andrzej LU ; Polishchuk, Valentin and Xue, Quan (2025) In Theoretical Computer Science 1055.
Abstract

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.... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Convex hull, Delaunay triangulation, Distributed algorithm, The congested clique model, Voronoi diagram
in
Theoretical Computer Science
volume
1055
article number
115491
publisher
Elsevier
external identifiers
  • scopus:105011843412
ISSN
0304-3975
DOI
10.1016/j.tcs.2025.115491
language
English
LU publication?
yes
id
90308551-1c84-403d-a205-359038754f82
date added to LUP
2025-10-29 10:50:42
date last changed
2025-10-29 10:51:51
@article{90308551-1c84-403d-a205-359038754f82,
  abstract     = {{<p>We study the problems of computing the Voronoi diagram and a triangulation of a set of n<sup>2</sup> 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 n<sup>2</sup> 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 n<sup>2</sup> 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.</p>}},
  author       = {{Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej and Polishchuk, Valentin and Xue, Quan}},
  issn         = {{0304-3975}},
  keywords     = {{Convex hull; Delaunay triangulation; Distributed algorithm; The congested clique model; Voronoi diagram}},
  language     = {{eng}},
  month        = {{11}},
  publisher    = {{Elsevier}},
  series       = {{Theoretical Computer Science}},
  title        = {{Deterministic protocols for Voronoi diagrams and triangulations of planar point sets on the congested clique}},
  url          = {{http://dx.doi.org/10.1016/j.tcs.2025.115491}},
  doi          = {{10.1016/j.tcs.2025.115491}},
  volume       = {{1055}},
  year         = {{2025}},
}