Evasion Paths in Mobile Sensor Networks

Wednesday, March 5, 2014 - 9:00am - 9:50am
Keller 3-180
Henry Adams (University of Minnesota, Twin Cities)
Suppose ball-shaped sensors wander in a bounded domain. A sensor doesn't know its location but does know when it overlaps a nearby sensor. We say that an evasion path exists in this sensor network if a moving intruder can avoid detection. Vin de Silva and Robert Ghrist give a necessary condition, depending only on the time-varying connectivity data of the sensors, for an evasion path to exist. Using zigzag persistent homology, we provide an equivalent condition that moreover can be computed in a streaming fashion. However, no method with time-varying connectivity data (i.e. Cech complexes) as input can give necessary and sufficient conditions for the existence of an evasion path. Indeed, we show that the existence of an evasion path depends on more than just the fibrewise homotopy type of the region covered by sensors. In the setting of planar sensors that also measure weak rotation information, we provide necessary and sufficient conditions for the existence of an evasion path, and we pose an open question concerning Cech and alpha complexes. Joint with Gunnar Carlsson.

The second part of my talk is joint work with Michal Adamaszek, Christopher Peterson, and Corrine Previte. We show that a Vietoris-Rips complex or a restricted Cech complex on a finite set of points from the circle is homotopy equivalent to either a point, an odd sphere, or a wedge sum of spheres of the same even dimension.
MSC Code: