A scalable parallel minimum spanning tree algorithm for catchment basin delimitation in large digital elevation models. (10th December 2012)

• Record Type: Journal Article
• Authors: Do, Hiep‐Thuan; Limet, Sébastien; Melin, Emmanuel; Smari, Waleed; Fiore, Sandro; Hill, David
• Is Part Of: Concurrency and computation. Volume 25:Number 10(2013:Jul.)
• Page Start: 1394
• Page End: 1409
• Publication Date: 2012-12-10
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.2950
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe2950-abs-0001"> <title>SUMMARY</title> <p>This paper describes a new fast and scalable parallel algorithm to automatically determine catchment basin of rivers in large digital elevation models (DEMs). This algorithm is based on the construction of a minimal spanning tree, via a hierarchy of graphs, modeling the water route on the DEM. It combines different techniques used in hydrogeology, image processing and graph theory to obtain the most accurate results in terms of geomorphology without any preprocessing. The method tends to exploit the most of the DEMs, avoiding misleading inconsistencies DEMs contain. It has been designed to be entirely parallel and scalable for architectures such as PC clusters. Some experiments are presented to show accuracy, efficiency and scalability on huge DEMs. Copyright © 2012 John Wiley &amp; Sons, Ltd.</p> </abstract>