Travail en commun avec
Gady Kozma (Weizmann Institute),
Micha Sharir (Tel Aviv University) et
Gideon Stupp (Technion).
Some of the first routing algorithms for geographically
aware wireless networks used the Delaunay triangulation among the
network's nodes as the underlying connectivity graph. These
solutions were considered impractical, however, because in general
the Delaunay triangulation may contain arbitrarily long edges, and
because calculating the Delaunay triangulation generally requires
a global view of the network. Many other algorithms were then
suggested for geometric routing, often assuming random placement
of network nodes for analysis or simulation. We show that, when
the nodes are uniformly placed in the unit disk, the Delaunay
triangulation does not contain long edges, it is easy to compute
locally and it is in many ways optimal for geometric routing and
flooding.