Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Jansson, Jesper LU ; Levcopoulos, Christos LU orcid ; Lingas, Andrzej LU and Xue, Quan (2025) 0th International Computing and Combinatorics Conference, COCOON 2024 In Lecture Notes in Computer Science (LNCS), 15162. p.478-489
Abstract
We study the problem of computing the Voronoi diagram 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.
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 .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 computed in.O(log n) rounds in this model.
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Computing and Combinatorics : 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part II - 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part II
series title
Lecture Notes in Computer Science (LNCS),
volume
15162
pages
478 - 489
publisher
Springer
conference name
0th International Computing and Combinatorics Conference, COCOON 2024
conference location
Shanghai, China
conference dates
2024-08-23 - 2024-08-25
external identifiers
  • scopus:86000459904
ISSN
1611-3349
0302-9743
ISBN
978-981-96-1092-1
978-981-96-1093-8
DOI
10.1007/978-981-96-1093-8_39
language
English
LU publication?
yes
id
b817445f-5bf2-4f07-9a8a-0f1e75a1ab5d
date added to LUP
2025-02-20 13:03:25
date last changed
2025-07-06 10:17:33
@inproceedings{b817445f-5bf2-4f07-9a8a-0f1e75a1ab5d,
  abstract     = {{We study the problem of computing the Voronoi diagram of a set of<br/>.n2 points with.O(log n)-bit coordinates in the Euclidean plane in a substantially<br/>sublinear in . n number of rounds in the congested clique model with . n nodes.<br/>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<br/>smoothness condition is satisfied by an input set of .n2 points with .O(log n)-bit<br/>coordinates in the unit square then the Voronoi diagram of the point set within the<br/>unit square can be computed in.O(log n) rounds in this model.}},
  author       = {{Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej and Xue, Quan}},
  booktitle    = {{Computing and Combinatorics : 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part II}},
  isbn         = {{978-981-96-1092-1}},
  issn         = {{1611-3349}},
  language     = {{eng}},
  month        = {{02}},
  pages        = {{478--489}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science (LNCS),}},
  title        = {{The Voronoi Diagram of Weakly Smooth Planar Point Sets in O(log n)  Deterministic Rounds on the Congested Clique}},
  url          = {{http://dx.doi.org/10.1007/978-981-96-1093-8_39}},
  doi          = {{10.1007/978-981-96-1093-8_39}},
  volume       = {{15162}},
  year         = {{2025}},
}