Distributed voronoi diagram computation in wireless sensor networks

ABSTRACT

We present a distributed algorithm to compute the Voronoi Diagram (VD) of a wireless network in the plane. Our contribution is twofold: the complete VD is computed, as opposed to the approximate or the bounded VD, and the number of transmissions used is relatively small.

REFERENCES

• 1: Boulat A. Bash , Peter J. Desnoyers, Exact distributed Voronoi cell computation in sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236393]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Distributed networks

General Terms:
Algorithms, Experimentation, Theory

Keywords:
distributed algorithms, sensor networks, voronoi diagrams