2011/07/26 by Aubin Jarry, Jarry, Aubin, Florian Huc +6
Computer Science · Engineering · #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Modular Robots and Swarm Intelligence #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #cs.NI
paper · pdf · doi:10.48550/arxiv.1107.5154
arxiv created 2011/07/26 · openalex publication_date 2011/07/26 · arxiv updated 2011/07/27 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of node's identifier sent by the algorithm is 6n, while the computational complexity is O(nΔ), with Δ the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph. Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as 3n node's identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of 5n broadcasts.