Single-Step Creation of Localized Delaunay Triangulations



A localized Delaunay triangulation owns the following interesting properties for sensor and wireless ad hoc networks: 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 two localized algorithms, FLDT1 and FLDT2, that build a graph called planar localized Delaunay triangulation, PLDel, known to be a good spanner of the Unit Disk Graph, UDG. Our algorithms improve previous algorithms with similar theoretical bounds in the following aspects: unlike previous work, FLDT1 and FLDT2 build PLDel in a single communication step, maintaining a communication cost of O(n log n), which is within a constant of the optimal. Additionally, we show that FLDT1 is more robust than previous triangulation algorithms, because it does not require the strict UDG connectivity model to work. The small signaling cost of our algorithms allows us to improve routing performance, by effciently using the PLDel graph instead of sparser graphs, like the Gabriel or the Relative Neighborhood graphs.


Mobile Ad Hoc Networks


Wireless Networks, Vol. 15, #7, pp. 845-858, Springer Netherlands, October 2009

PDF File

Cited by

Year 2012 : 1 citations

 Daza-Rodriguez, J.C.; Florez-Valencia, L., "3D meshing algorithm based on analytical curvatures," Informatica (CLEI), 2012 XXXVIII Conferencia Latinoamericana En , vol., no., pp.1,6, 1-5 Oct. 2012
doi: 10.1109/CLEI.2012.6427122
keywords: {Gaussian processes;computational geometry;mesh generation;3D meshing algorithm;Delaunay triangulations;RGC model;analytical Gaussian curvatures;analytical mean curvatures;continuous differentiable functions;quality criteria;right generalized cylinder model;surface representation;Biological system modeling;Computational modeling;Electronic mail;Indexes;Media;Solid modeling;Vectors;Delaunay triangulation;curvature;gaussian curvature;mean curvature;mesh},

Year 2011 : 1 citations

 Delaunay triangulation as a new coverage measurement method in wireless sensor network H Chizari, M Hosseini, T Poston, SA Razak… Sensors 2011

Year 2010 : 1 citations

 Communication-efficient construction of the plane localized delaunay graph P Bose, P Carmi, M Smid, D Xu LATIN 2010: Theoretical Informatics 2010