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

Math @ Duke



Publications [#235497] of Pankaj K. Agarwal

Papers Published

  1. Danner, A; Mølhave, T; Yi, K; Agarwal, PK; Arge, L; Mitasova, H, TerraStream: From elevation data to watershed hierarchies, Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems (December, 2007), pp. 212-219 [doi]
    (last updated on 2018/12/13)

    We consider the problem of extracting a river network and a watershed hierarchy from a terrain given as a set of irregularly spaced points. We describe TERRASTREAM, a "pipelined" solution that consists of four main stages: construction of a digital elevation model (DEM), hydrological conditioning, extraction of river networks, and construction of a watershed hierarchy. Our approach has several advantages over existing methods. First, we design and implement the pipeline so that each stage is scalable to massive data sets; a single non-scalable stage would create a bottleneck and limit overall scalability. Second, we develop the algorithms in a general framework so that they work for both TIN and grid DEMs. Furthermore, TERRASTREAM is flexible and allows users to choose from various models and parameters, yet our pipeline is designed to reduce (or eliminate) the need for manual intervention between stages. We have implemented TERRASTREAM and we present experimental results on real elevation point sets, which show that our approach handles massive multi-gigabyte terrain data sets. For example, we can process a data set containing over 300 million points - -over 20GB of raw data - -in under 26 hours, where most of the time (76%) is spent in the initial CPU-intensive DEM construction stage. © 2007 ACM.
ph: 919.660.2800
fax: 919.660.2821

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