de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Hole Detection or: "How Much Geometry Hides in Connectivity?"

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44793

Klein,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Funke, S., & Klein, C. (2006). Hole Detection or: "How Much Geometry Hides in Connectivity?". In Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06 (pp. 377-385). New York, USA: ACM.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2316-2
Zusammenfassung
Wireless sensor networks typically consist of small, very simple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly, but have no idea about their relative geographic locations. We examine how much geometry information is nevertheless hidden in the communication graph of the network: Assuming that the connectivity is determined by the well-known unit-disk graph model, we prove that using an extremely simple linear-time algorithm one can identify nodes on the boundaries of holes of the network. That is, there is enough geometry information hidden in the connectivity structure to identify topological features -- in our example the holes in the network. While the theoretical analysis turns out to be quite conservative, an actual implementation shows that the algorithm works well under less stringent conditions.