Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.authorAraújo, Filipe-
dc.contributor.authorRodrigues, Luís-
dc.identifier.citationARAÚJO, Filipe; RODRIGUES, Luís - Single-Step Creation of Localized Delaunay Triangulations. Coimbra : CISUC, 2006. (CISUC, TR-3)en_US
dc.description.abstractA 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, P LDel, 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 P LDel 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 efficiently using the P LDel graph instead of sparser graphs, like the Gabriel or the Relative Neighborhood graphs.en_US
dc.publisherUnivesity of Coimbra. Centre for Informatics and Systemsen_US
dc.subjectWireless communicationen_US
dc.subjectRouting protocolsen_US
dc.subjectDelaunay triangulationen_US
dc.titleSingle-Step Creation of Localized Delaunay Triangulationsen_US
degois.publication.titleSingle-Step Creation of Localized Delaunay Triangulationsen_US
item.fulltextCom Texto completo-
item.languageiso639-1en- de Ciências e Tecnologia, Universidade de Coimbra- de Coimbra- FOR INFORMATICS AND SYSTEMS OF THE UNIVERSITY OF COIMBRA-
Appears in Collections:FCTUC Eng.Informática - Relatórios Técnicos
Files in This Item:
File Description SizeFormat
Single-Step Creation of Localized Delaunay Triangulations.pdf334.06 kBAdobe PDFView/Open
Show simple item record

Page view(s)

checked on Dec 2, 2020

Download(s) 50

checked on Dec 2, 2020

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.