Math @ Duke

Publications [#323790] of Pankaj K. Agarwal
Papers Published
 Nath, A; Fox, K; Agarwal, PK; Munagala, K, Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains,
GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
(October, 2016), ISBN 9781450345897 [doi]
(last updated on 2018/07/16)
Abstract: © 2016 ACM. We propose parallel algorithms in the massively parallel communication (MPC) model (e.g. MapReduce) for processing large terrain elevation data (represented as a 3D point cloud) that are too big to fit on one machine. In particular, given a set S of 3D points that is distributed across multiple machines, we present a simple randomized algorithm to construct a TIN DEM of S by computing the Delaunay triangulation of the xyprojections of points in S, which is also stored across multiple machines. With high probability, the algorithm works in O(1) rounds and the total work performed is O(n log n). Next, we describe an efficient algorithm in the MPC model for computing the contour tree of the resulting DEM. Under some assumptions on the input, the algorithm works in O(1) rounds and the total work performed is O(n log n).


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

