Finding Bottlenecks in Tunnels using Topology and Optimization

Sensor nodes are often used to guard 3D domains against intrusion by a foreign object. We have to compute the size of bottlenecks in any tunnels in the space being monitored. Coverage against intrusion is guaranteed if bottlenecks of such tunnels are not big enough to let the object go through. Similar computations are employed in designing certain proteins, where access to the active site for the reacting small molecule is through tunnels. Other related applications arise in closing holes in cellphone coverage maps, and in computer aided design (CAD). This talk will present a low level introduction to some recently discovered connections between discrete optimization and algebraic topology, which help in solving such problems efficiently.