Fast and Efficient Restricted Delaunay Triangulation in Random Geometric Graphs
Chen Avin ยท Internet Mathematics ยท 2008
Let _G_ = ๐(_n, r_) be a random geometric graph resulting from placing _n_ nodes uniformly at random in the unit square (or the unit disk) and connecting every two nodes if and only if their Euclidean distance is at most _r_. Let be the known critical radius for connectivity when _n_ โ โ. The _restricted Delaunay graph_ RDG(_G_) is a subgraph of _G_ with the following properties: it is a planar graph and a spanner of _G_, and in particular it contains all the short edges of the Delaunay triangulation of _G_. While in general graphs, the construction of RDG(_G_) requires ฮ(_n_) messages, we show that when _r_ = _O_(_r_con) and _G_ = ๐(_n, r_), then with high probability, RDG(_G_) can be constructed locally in one round of communication with messages, and with only one-hop neighborhood information. This size of _r_ proves that the existence of long Delaunay edges (an order larger than _r_con) in the unit square (disk) does not significantly affect the efficiency with which good routing graphs can be maintained.