MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Funke, Stefan
Klein, Christian		dblp
dblp
Editor(s):
Amenta, Nina
Cheong, Otfried		dblp
dblp
Not MPII Editor(s):
Amenta, Nina
Cheong, Otfried
BibTeX cite key*:
FK2006
Title, Booktitle
Title*:
Hole Detection or: "How Much Geometry Hides in Connectivity?"
paper.pdf (1184.74 KB)
Booktitle*:
Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06
Event, URLs
Conference URL::
Downloading URL:
http://delivery.acm.org/10.1145/1140000/1137911/p377-funke.pdf?key1=1137911&key2=3613680711&coll=GUIDE&dl=GUIDE&CFID=13792799&CFTOKEN=15613582
Event Address*:
Sedona, Arizona, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
5 June 2006
Event End Date:
7 June 2006
Publisher
Name*:
ACM
URL:
http://www.acm.org/
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
377-385
Year*:
2006
VG Wort Pages:
47
ISBN/ISSN:
1-59593-340-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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.
URL for the Abstract:
http://portal.acm.org/citation.cfm?doid=1137856.1137911
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{FK2006,
AUTHOR = {Funke, Stefan and Klein, Christian},
 EDITOR = {Amenta, Nina and Cheong, Otfried},
 TITLE = {Hole Detection or: "How Much Geometry Hides in Connectivity?"},
 BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06},
 PUBLISHER = {ACM},
 YEAR = {2006},
 PAGES = {377--385},
 ADDRESS = {Sedona, Arizona, USA},
 ISBN = {1-59593-340-9},
}

Entry last modified by Regina Kraemer, 04/16/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christian Klein		Created
01/09/2007 15:03:27
Revisions
6.
5.
4.
3.
2.		Editor(s)
Regina Kraemer
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
04/16/2007 09:55:41 AM
2007-04-11 11:15:39
07.02.2007 19:12:37
07.02.2007 19:09:21
07.02.2007 19:08:53

File Attachment Icon
paper.pdf