Some problems in distributed computational geometry

AbstractIn a planar geometric network vertices are located in the plane, and edges are straight line segments connecting pairs of vertices, such that no two of them intersect. In this paper we study distributed computing in asynchronous, failure-free planar geometric networks, where each vertex is associated to a processor, and each edge to a bidirectional message communication link. Processors are aware of their locations in the plane.We consider fundamental computational geometry problems from the distributed computing point of view, such as finding the convex hull of a geometric network and identification of the external face. We also study the classic distributed computing problem of leader election, to understand the impact that geometric information has on the message complexity of solving it.We obtain an O(nlog2n) message complexity algorithm to find the convex hull, and an O(nlogn) message complexity algorithm to identify the external face of a geometric network of n processors. We present a matching lower bound for the external face problem. We prove that the message complexity of leader election in a geometric ring is Ω(nlogn), hence geometric information does not help in reducing the message complexity of this problem