Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#311264] of John Harer

Papers Published

  1. Munch, E; Shapiro, M; Harer, J, Failure filtrations for fenced sensor networks, International Journal of Robotics Research, vol. 31 no. 9 (August, 2012), pp. 1044-1056 [1109.6535v1], [doi]
    (last updated on 2018/12/15)

    In this paper we consider the question of sensor network coverage for a 2-dimensional domain. We seek to compute the probability that a set of sensors fails to cover given only non-metric, 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 #P-complete, 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320