Rips complexes of spherical cows

At WADS last summer Jeff Erickson gave a nice talk about Rips complexes, which I also posted about here a while back, and last month Jeff and his co-authors posted their preprint to the arxiv, at which point I dumped it in my folder of recent arxiv preprints that I should really read and try to understand someday. But then it was the holidays and I got busy with other stuff and I didn't get around to looking at it until now, when Jeff and his student Erin Chambers (another of the preprint co-authors) are visiting and I could just ask them to tell me what's in it rather than having to take the trouble to read it myself.

The motivating problem here is distributed sensor networks: one imagines scattering randomly a collection of low-power wireless computing devices over some area, letting them talk to each other, and from that information figuring out the shape of the area they've been spread over. In the oversimplified theoretical model of such networks, two devices can talk to each other if they're within some threshold distance D of each other, and can't talk to each other otherwise, giving a unit disk graph. Once one strips out the topological definitions, Chambers et al propose the following model for reconstructing the shape of the point set from this graph: form a triangle for every three devices that can talk to each other in pairs, and a line segment for every two devices that can talk to each other, take the union of these geometric objects (the “shadow of the Rips complex”), and use that as your approximation to the shape of the points. The nice theorem is that the shadow has the same fundamental group as the Rips complex itself, so that the Rips complex is useful for computing topological information about the shape of the points in a nice coordinate-free way. In some other papers some permutation of these authors also find an efficient algorithm for computing shadows and for testing contractability of cycles on Rips complexes (or equivalently, by their other results, in their shadows).

So that's the good news. The bad news: this all doesn't really work for the sensor network problems. We've made too many assumptions that don't make sense in that application. One of those assumptions, made in the results on algorithms for testing contractability and computing shadows, is that we know the coordinates of the points. But in the sensor network application, the whole difficulty is that we don't know the coordinates — if we did, there are plenty of more direct methods of reconstructing shapes — we want to reconstruct the shape of a point set in a coordinate-free way, and the Rips complex is defined in a nice coordinate-free way but that freedom doesn't extend to the algorithms.

The second bad assumption is that the sensors can talk to each other exactly when they're within D of each other. Really, there's some threshold within which they can talk to each other, some larger threshold beyond which they can't talk to each other, and between those two thresholds they may or may not be able to communicate. To understand this more complex behavior, Chambers et al define a quasi-Rips complex, the flag complex (family of simplices defined from complete subgraphs) of a graph that has edges with the same thresholding behavior. But it turns out (section 4 of the arxiv preprint) that quasi-Rips complexes are a lot less well-behaved than Rips complexes. The fundamental groups of planar regions, and of Rips complexes of planar point sets, are always free, but the fundamental groups of quasi-Rips complexes of planar point sets can be (modulo a free factor) any finitely presented group. The construction involves placing many points in three tightly packed clusters near each of the three corners of an equilateral triangle, allowing the graph from which the quasi-Rips complex is formed to be the complement of an arbitrary tripartite graph.

The upshot of which is that, although interesting as abstract computational topology, it's not yet clear whether the pretty theory can be applied to the practical problems that motivated it. At the least, more work is needed, either smoothing away the topological problems of the quasi-Rips complex or showing that they only arise for unlikely configurations of points, and allowing the algorithms to run even in the absence of coordinates.

Comments: