Distributed Algorithms for Voronoi Diagrams and Applications in Ad-hoc Networks

The Voronoi diagram is a fundamental structure in computational geometry and arises naturally in many applications including wireless networking. In this paper, we propose a distributed algorithm by which each node u can compute its Voronoi region in O(d(u)) time, where d(u) is the number of the Voronoi neighbors of node u. Then we show how the algorithm can be applied in topology control of wireless ad-hoc networks, and also propose a revised version of the algorithm to minimize transmission energy consumption. Further applications of the algorithm in different areas are expected.National Science FoundationOpe