Convex Hulls, Triangulations, and Voronoi Diagrams of Planar Point Sets on the Congested Clique

2023/05/17 by Jesper Jansson, Christos Levcopoulos, Jansson, Jesper +4
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Distributed #F.2.2 #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Parallel #Topological and Geometric Data Analysis #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2305.09987

openalex publication_date 2023/05/17 · openalex created_date 2023/05/20 · openalex updated_date 2026/08/01

Abstract

We consider geometric problems on planar n²-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 O(log n)-bit coordinates. In each round, each node can send a distinct O(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 n²-point set can be constructed in O(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 n²-point set can be constructed in O(log²n) rounds on the congested clique. Finally, we demonstrate that the Voronoi diagram of n² points with O(log n)-bit coordinates drawn uniformly at random from a unit square can be computed within the square with high probability in O(1) rounds on the congested clique.

Related

• The Voronoi Diagram of Weakly Smooth Planar Point Sets in O(log n) Deterministic Rounds on the Congested Clique
• Planar Voronoi Diagrams for Sums of Convex Functions, Smoothed Distance and Dilation
• Revisiting Random Points: Combinatorial Complexity and Algorithms
• Weighted Poisson-Delaunay Mosaics
• A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations