Math @ Duke

Publications [#311264] of John Harer
Papers Published
 Munch, E; Shapiro, M; Harer, J, Failure filtrations for fenced sensor networks,
International Journal of Robotics Research, vol. 31 no. 9
(August, 2012),
pp. 10441056 [1109.6535v1], [doi]
(last updated on 2018/11/18)
Abstract: In this paper we consider the question of sensor network coverage for a
2dimensional domain. We seek to compute the probability that a set of sensors
fails to cover given only nonmetric, local (who is talking to whom)
information and a probability distribution of failure of each node. This builds
on the work of de Silva and Ghrist who analyzed this problem in the
deterministic situation. We first show that a it is part of a slightly larger
class of problems which is #Pcomplete, and thus fast algorithms likely do not
exist unless P$=$NP. We then give a deterministic algorithm which is feasible
in the case of a small set of sensors, and give a dynamic algorithm for an
arbitrary set of sensors failing over time which utilizes a new criterion for
coverage based on the one proposed by de Silva and Ghrist. These algorithms
build on the theory of topological persistence.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

