Communication costs in a geometric communication network

DOI10.1016/J.TCS.2023.114161MaRDI QIDQ6052702zbMATH OpenOpenAlexFDO

Authors Sima Hajiaghaei Shanjani, Valerie King

Publication date 17 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.13499

zbMATH Keywords

closest paircommunication complexityCONGESTconvex hulldistributed algorithmfarthest pair

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A communication network is a graph in which each node has only local information about the graph and nodes communicate by passing messages along its edges. Here, we consider the {it geometric communication network} where the nodes also occupy points in space and the distance between points is the Euclidean distance. Our goal is to understand the communication cost needed to solve several fundamental geometry problems, including Convex Hull, Diameter, Closest Pair, and approximations of these problems, in the asynchronous CONGEST KT1 model. This extends the 2011 result of Rajsbaum and Urrutia for finding a convex hull of a planar geometric communication network to networks of arbitrary topology.

Cites work

• A trade-off between information and communication in broadcast protocols
• An almost space-optimal streaming algorithm for coresets in fixed dimensions
• Approximate convex hull of data streams
• Approximate MST for UDG locally
• Approximating extent measures of points.
• Better -dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and -kernels
• Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
• Circles passing through five or more integer points
• Communication Complexity
• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MST and broadcast with fewer messages, and faster gossiping
• DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
• Distributed verification and hardness of distributed approximation
• Distributed verification and hardness of distributed approximation
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• scientific article; zbMATH DE number 6696541 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• On the Complexity of Universal Leader Election
• On the complexity of universal leader election
• On the distributional complexity of disjointness
• Routing with guaranteed delivery in ad hoc wireless networks
• Some problems in distributed computational geometry
• The Probabilistic Communication Complexity of Set Intersection
• Time-message trade-offs in distributed algorithms

Cited in

(2)

• Communication aspects of networks based on geometric incidence relations
• Communication and location discovery in geometric ring networks

This page was built for publication: Communication costs in a geometric communication network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052702)