English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Hole Detection or: "How Much Geometry Hides in Connectivity?"

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2316-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2317-F
Genre: Conference Paper

Files

show Files
hide Files
:
paper.pdf (Any fulltext), 2MB
 
File Permalink:
-
Name:
paper.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Funke, Stefan1, Author           
Klein, Christian1, Author           
Amenta, Nina, Editor
Cheong, Otfried, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-162006
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314452
Other: Local-ID: C1256428004B93B8-501E6A40DCBD9F35C125725E004D389A-FK2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Sedona, Arizona, USA
Start-/End Date: 2006-06-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 377 - 385 Identifier: ISBN: 1-59593-340-9