Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains

Published

Conference Paper

© 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 xy-projections 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).

Full Text

Duke Authors

Cited Authors

  • Nath, A; Fox, K; Agarwal, PK; Munagala, K

Published Date

  • October 31, 2016

Published In

  • Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems

International Standard Book Number 13 (ISBN-13)

  • 9781450345897

Digital Object Identifier (DOI)

  • 10.1145/2996913.2996952

Citation Source

  • Scopus