Math @ Duke

Publications [#354199] of Pankaj K. Agarwal
Papers Published
 Lowe, A; Svendsen, SC; Agarwal, PK; Arge, L, 1D and 2D Flow Routing on a Terrain,
Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems
(November, 2020),
pp. 514 [doi]
(last updated on 2021/05/17)
Abstract: An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of flowquery related problems: given a terrain Σ represented as a triangulated xymonotone surface with n vertices, and a rain distribution R which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internalmemory as well as I/Oefficient algorithms for flow queries. This paper contains four main results: (i) An internalmemory algorithm for answering terrainflow queries: preprocess Σ into a linearsize data structure so that given a rain distribution R the flowrate functions of all edges of Σ can be reported quickly. (ii) I/Oefficient algorithms for answering terrainflow queries. (iii) An internal memory algorithm for answering edgeflow queries: preprocess Σ into a linearsize data structure so that given a rain distribution R, the flowrate function of an edge under the singleflow direction (SFD) model can be computed quickly. (iv) We present an efficient algorithm that given a path in Σ computes the twodimensional channel along which water flows.


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

