Coverage in sensor networks via persistent homology

2007/04/25 by Vin de Silva, Robert Ghrist · 434 citations
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Homotopy and Cohomology in Algebraic Topology #Mathematics #Persistent homology #Homology (biology) #Topology (electrical circuits) #Combinatorics #Genetics #Algorithm #Biology #Gene

paper · pdf · doi:10.2140/agt.2007.7.339

published in Algebraic & Geometric Topology 7(1), 339-358 (Mathematical Sciences Publishers)

openalex publication_date 2007/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/09

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.

Citations

• Topological estimation using witness complexes
• Differential Forms in Algebraic Topology
• �ber den h�heren Zusammenhang kompakter R�ume und eine Klasse von zusammenhangstreuen Abbildungen
• Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology
• Computing Persistent Homology
• Hyperbolic Groups

Cited by

• A fast algorithm for constructing topological structure in large data
• Topological data analysis [wikipedia]