Premium
A scalable parallel minimum spanning tree algorithm for catchment basin delimitation in large digital elevation models
Author(s) -
Do HiepThuan,
Limet Sébastien,
Melin Emmanuel
Publication year - 2013
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.2950
Subject(s) - digital elevation model , scalability , computer science , preprocessor , exploit , elevation (ballistics) , graph , spanning tree , drainage basin , algorithm , tree (set theory) , remote sensing , theoretical computer science , geology , artificial intelligence , mathematics , database , cartography , geography , computer security , geometry , combinatorics , mathematical analysis
SUMMARY 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 & Sons, Ltd.