In their seminal work on homological sensor networks, de Silva and Ghrist showed the surprising fact that it's possible to certify the coverage of a coordinate-free sensor network even with very minimal knowledge of the space to be covered. Here, coverage means that every point in the domain (except possibly those very near the boundary) has a nearby sensor. More generally, their algorithm takes a pair of nested neighborhood graphs along with a labeling of vertices as either boundary or interior and computes the relative homology of a simplicial complex induced by the graphs. This approach, called the Topological Coverage Criterion (TCC), requires some assumptions about the underlying geometric domain as well as some assumptions about the relationship of the input graphs to the domain. The goal of this paper is to generalize these assumptions and show how the TCC can be applied to both much more general domains as well as very weak assumptions on the input. We give a new, simpler proof of the de Silva-Ghrist Topological Coverage Criterion that eliminates any assumptions about the smoothness of the boundary of the underlying space, allowing the results to be applied to much more general problems. The new proof factors the geometric, topological, and combinatorial aspects, allowing us to provide a coverage condition that supports thick boundaries, k-coverage, and weighted coverage, in which sensors have varying radii. Problems in Homological Sensor Networks (HSNs) are usually stated in the vocabulary of sensor networks. There are sensors and coverage regions, and an important problem is to determine if the sensing region of a collection of sensors covers a given domain, given only the neighborhood relationships between the sensors and some indication of which sensors are near the boundary. The locations (coordinates) of the points is not assumed, nor is the shape (topology) of the domain to be covered. Although phrased in the language of sensor networks, the problem may be understood more generally as one of data coverage; it answers when a data set * Supported by NSF grants CCF-1464379 and CCF-1525978. † University of Connecticut. ‡ University of Connecticut. § University of Connecticut. sufficiently covers a domain, and holes in coverage can be viewed as gaps in the data. A surprising result by de Silva & Ghrist is that there exists a computable, sufficient condition called the Topological Coverage Criterion (TCC) to certify coverage without knowing the locations of the sensors when the domain's boundary is smooth [4] . All that is required is that the sensors have unique identifiers, can detect nearby sensors, can differentiate whether neighboring sensors are "close" or "very close" (in a technical sense to be defined below), and can detect if the boundary of the domain is close. Developed over a series of papers [8, 17, 5, 4] , the most general version of the TCC can be understood as a purely geometric problem on point sets P in R d with unknown coordinates in an unknown domain D. The input is just a pair of nested neighborhood graphs on the points indicating which points are close to which others and a labeling of the points indicating which points are close to the boundary of D. Determining coverage is ill-posed with only this information, but de Silva & Ghrist proved that the TCC gives a sufficient condition for coverage (of a slightly shrunken version) of the domain when the radii are all equal, the boundary of the domain is a smooth manifold with bounded injectivity radius, and the goal is to certify single-coverage (each point covered by at least one sensor). In this paper, we generalize these results in several directions, most notably in eliminating many of the geometric assumptions on the domain, while also certifying multiple-coverage and allowing for varying radii. For an input graph G = (P, E) where P is a set of points, and a subset Q ⊆ P of points labeled as near the boundary, the TCC algorithm builds a pair of simplicial complexes, one from the cliques in G and one from the cliques in the subgraph of G induced by Q. By a straightforward matrix reduction, a vector space called the relative d-dimensional homology of this nested pair of subcomplexes can be computed. In an ideal situation, the dimension would indicate exactly the number of connected components if and only if the domain is covered. However, this simplistic approach does not work in general, because it can detect spurious components. The insight of de Silva and Ghrist was to show that for sufficiently nice geometric
Cavanna et al. REF recently generalized the assumptions on the boundaries to make the results applicable to general domains.
When and why the topological coverage criterion works
SODA
Computer Science