Exact and approximate computations of watersheds on triangulated terrains

K. Tsirogiannis, M.T. Berg, de

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS 2011, Chicago IL, USA, November 1-4, 2011)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)978-1-4503-1031-4
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Exact and approximate computations of watersheds on triangulated terrains'. Together they form a unique fingerprint.

Cite this