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

Conference Paper

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