Distributed computation of Voronoi diagrams in wireless networks

Yurai Rodriguez

Voronoi diagrams have multiple applications in wireless networks. For example, in wireless sensor networks Voronoi diagrams are used for solving sensing, tracking, and coverage problems. We study the problem of computing Voronoi diagrams distributedly in a connected wireless network. Existing algorithms compute different approximations to Voronoi diagrams and, in some cases, are very expensive in terms of communication cost. We propose an algorithm that correctly computes the complete Voronoi diagram and uses a significantly smaller number of transmissions as compared to other approaches. Furthermore, other useful geometric structures such as the Delaunay triangulation and the convex hull of the network can be obtained through our algorithm at no extra communication cost.