Fast Localized Delaunay Triangulation.
F. Araújo, and L. Rodrigues
Selected sections of this report will be published in the Proceedings
of the Proceedings of the 8th International Conference on Principles
of Distributed Systems (OPODIS), December 15-17 2004, Grenoble,
France.
Abstract
A localized Delaunay triangulation owns the following interesting
properties in a wireless ad hoc setting: it can be built with
localized information, the communication cost imposed by control
information is limited and it supports geographical routing algorithms
that offer guaranteed convergence. This paper presents a localized
algorithm that builds a graph called planar localized Delaunay
triangulation, PLDel, known to be a good spanner of the unit
disk graph, UDG. Unlike previous work, our algorithm builds
PLDel in a single communication step, maintaining a
communication cost of O(n \log n), which is within a constant
of the optimum. This represents a significant practical improvement
over previous algorithms with similar theoretical bounds. Furthermore,
the small cost of our algorithm makes feasible to use $PLDel$ in real
systems, instead of the Gabriel or the Relative Neighborhood graphs,
which are not good spanners of UDG.
Also available extended report (gzip postscript), (pdf) .
Luís Rodrigues