Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique.

Jansson, Jesper LU ; Levcopoulos, Christos LU orcid and Lingas, Andrzej LU (2023) 35th Canadian Conference on Computational
Geometry, CCCG 2023 p.183-189
Abstract
We consider geometric problems on planar n2-point sets in the congested clique model. Initially, each node in the n-clique network holds a batch of n distinct points in the Euclidean plane given by Ο(log n)-bit coordinates. Ineach round, each node can send a distinct Ο(log n)-bit message to each other node in the clique and perform unlimited local computations. We show that the convex hull of the input n2-point set can be constructed in Ο(min{h, log n}) rounds, where h is the size of the hull, on the congested clique. We also show that a triangulation of the input n2 -point set can be constructed in Ο(log2n) rounds on the... (More)
We consider geometric problems on planar n2-point sets in the congested clique model. Initially, each node in the n-clique network holds a batch of n distinct points in the Euclidean plane given by Ο(log n)-bit coordinates. Ineach round, each node can send a distinct Ο(log n)-bit message to each other node in the clique and perform unlimited local computations. We show that the convex hull of the input n2-point set can be constructed in Ο(min{h, log n}) rounds, where h is the size of the hull, on the congested clique. We also show that a triangulation of the input n2 -point set can be constructed in Ο(log2n) rounds on the congested clique. (Less)
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
Proceedings of the 35th Canadian Conference on Computational Geometry, CCCG 2023, Concordia University, Montreal, Quebec, Canada, July 31 - August 4, 2023.
pages
7 pages
conference name
35th Canadian Conference on Computational<br/>Geometry, CCCG 2023
conference location
Montreal, Canada
conference dates
2023-07-31 - 2023-08-04
language
English
LU publication?
yes
id
4adf32be-356c-4f6f-b543-e34fbb2959bf
alternative location
https://cccg.ca/proceedings/2023/CCCG2023.pdf
date added to LUP
2024-08-04 09:44:55
date last changed
2024-08-06 17:03:45
@inproceedings{4adf32be-356c-4f6f-b543-e34fbb2959bf,
  abstract     = {{We consider geometric problems on planar <i>n</i><sup>2</sup>-point sets in the congested clique model. Initially, each node in the <i>n</i>-clique network holds a batch of <i>n</i> distinct points in the Euclidean plane given by Ο(log <i>n</i>)-bit coordinates. Ineach round, each node can send a distinct Ο(log <i>n</i>)-bit message to each other node in the clique and perform unlimited local computations. We show that the convex hull of the input <i>n</i><sup>2-</sup>point set can be constructed in Ο(min{<i>h</i>, log <i>n</i>}) rounds, where h is the size of the hull, on the congested clique. We also show that a triangulation of the input <i>n</i><sup>2 </sup>-point set can be constructed in Ο(log<sup>2</sup><i>n</i>) rounds on the congested clique.}},
  author       = {{Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej}},
  booktitle    = {{Proceedings of the 35th Canadian Conference on Computational Geometry, CCCG 2023, Concordia University, Montreal, Quebec, Canada, July 31 - August 4, 2023.}},
  language     = {{eng}},
  pages        = {{183--189}},
  title        = {{Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique.}},
  url          = {{https://cccg.ca/proceedings/2023/CCCG2023.pdf}},
  year         = {{2023}},
}