Paper Info
Title
Exact and approximate computations of watersheds on triangulated terrains
Abstract
The natural way of modeling water flow on a triangulated terrain is to make the fundamental assumption that water follows the direction of steepest descent (dsd). However, computing watersheds and other flow-related structures according to the dsd model in an exact manner is difficult: the dsd model implies that water does not necessarily follow terrain edges, which makes designing exact algorithms difficult and causes robustness problems when implementing them. As a result, existing software implementations for computing watersheds are inexact: they either assume a simplified flow model or they perform computations using inexact arithmetic, which leads to inexact and sometimes inconsistent results. We perform a detailed study of various issues concerning the exact or approximate computation of watersheds according to the dsd model. Our main contributions are the following. • We provide the first implementation that computes watersheds on triangulated terrains following strictly the dsd model and using exact arithmetic, and we experimentally investigate its computational cost. Our experiments show that the algorithm cannot handle large data sets effectively, due to the bit-sizes needed in the exact computations and the computation of an intermediate structure called the strip map. • Using our exact algorithm as a point of reference, we evaluate the quality of several existing heuristics for computing watersheds. We also investigate hybrid methods, which use heuristics in a first phase of the algorithm and exact computation in a second phase. The hybrid methods are almost as fast as the heuristics, but give significantly more accurate results. • We describe and theoretically analyze a new exact algorithm for computing watersheds, which avoids the computation of the strip map.
Year
DOI
Venue
2011
10.1145/2093973.2093985
advances in geographic information systems
Keywords
DocType
Citations 
exact arithmetic,hybrid method,dsd model,flow model,exact computation,approximate computation,triangulated terrains,new exact algorithm,strip map,exact algorithm,exact manner,steepest descent
Conference
2
PageRank 
References 
Authors
0.39
7
2
Name
Order
Citations
PageRank
Mark De Berg11497153.24
Constantinos Tsirogiannis2125.93