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.


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