Math @ Duke

Publications [#332953] of Pankaj K. Agarwal
Papers Published
 Rav, M; Lowe, A; Agarwal, PK, Flood Risk Analysis on Terrains,
Proceedings of the 25th Acm Sigspatial International Conference on Advances in Geographic Information Systems Sigspatial'17, vol. 2017November
(2017), ACM Press, ISBN 9781450354905 [doi]
(last updated on 2019/01/24)
Abstract: © 2017 Copyright held by the owner/author(s). An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study the flooding query problem: Given a rain region R and a query point q on the terrain, quickly determine how much rain has to fall in R so that q is flooded. Available terrain data is often subject to uncertainty which must be incorporated into the terrain analysis. For instance, the digital elevation models of terrains have to be refined to incorporate underground pipes, tunnels, and waterways under bridges, but there is often uncertainty in their existence. By representing the uncertainty in the terrain data explicitly, we can develop methods for flood risk analysis that properly incorporate terrain uncertainty when reporting what areas are at risk of flooding. We present two results. First, we present a linear size data structure that given a terrain (with no data uncertainty) can answer the flooding query in O(m log 2 n) time, where m is the number of minima of the terrain at which rain is falling and n is the number of vertices of the terrain. Next, we extend this data structure to handle “uncertain” terrains, using a standard Monte Carlo method. Given a probability distribution on terrains, our data structure solves the problem of determining the probability that if a specified amount of rain falls on a given region a query point is flooded. We implement our data structures and show that they work very well in practice.


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

