Coverage in sensor networks via persistent homology

de Silva, Vin; Ghrist, Robert

doi:10.2140/agt.2007.7.339

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the Journal

Editorial Board

Subscriptions

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1472-2739 (online)

ISSN 1472-2747 (print)

Author Index

To Appear

Other MSP Journals

Coverage in sensor networks via persistent homology

Vin de Silva and Robert Ghrist

Algebraic & Geometric Topology 7 (2007) 339–358

DOI: 10.2140/agt.2007.7.339

Abstract

We introduce a topological approach to a problem of covering a region in Euclidean space by balls of fixed radius at unknown locations (this problem being motivated by sensor networks with minimal sensing capabilities). In particular, we give a homological criterion to rigorously guarantee that a collection of balls covers a bounded domain based on the homology of a certain simplicial pair. This pair of (Vietoris–Rips) complexes is derived from graphs representing a coarse form of distance estimation between nodes and a proximity sensor for the boundary of the domain. The methods we introduce come from persistent homology theory and are applicable to nonlocalized sensor networks with ad hoc wireless communications.

Keywords

Rips complex, Cech complex, persistent homology, sensor network, coverage

Mathematical Subject Classification 2000

Primary: 55M25, 93A15

Secondary: 55N35

References

Publication

Received: 25 November 2005

Revised: 29 January 2006

Accepted: 8 October 2006

Published: 25 April 2007

Authors

Vin de Silva
Department of Mathematics and Computer Science Pomona College Claremont CA 91711 USA

Robert Ghrist
Department of Mathematics and Coordinated Sciences Laboratory University of Illinois Urbana, IL 61801 USA

Volume 7, issue 1 (2007)