Let V be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane 4π√3/9-spanner of the unit-disk graph . Each node can only communicate with nodes that are within unit-distance from it. This algorithm only makes one round of communication and each point of V broadcasts at most 5 messages. This improves on all previously known message-bounds for this problem.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-12200-2_26
Citation
Bose, P, Carmi, P. (Paz), Smid, M, & Xu, D. (Daming). (2010). Communication-efficient construction of the plane localized Delaunay graph. doi:10.1007/978-3-642-12200-2_26