Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 03:03:27 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
paper.pdf