River networks and watershed maps of triangulated terrains revisited

H.K. Ahn, M. Berg, de, O. Cheong, H.J. Haverkort, A.F. van der Stappen, L. Toma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


Triangulated surfaces are often used to represent ter- rains in geographic information systems. We investi- gate the complexity of river networks and watershed maps on such terrains under the assumption that wa- ter always follows the path of steepest descent. We show that the worst-case complexity is only ??(n2) if all triangles are non-obtuse or if all triangles are fat, that is, their minimum angles are bounded from below by a positive constant. Furthermore, we can compute the river networks and watershed maps by tracing paths in a directed acyclic graph representa- tion of the triangulation—a property that can be ex- ploited to do computations I/O-efficiently.
Original languageEnglish
Title of host publicationAbstracts 22nd European Workshop on Computational Geometry (EWCG 2006, Delphi, Greece, March 27-29, 2006)
EditorsI. Emiris, M. Karavelas, L. Palios
Publication statusPublished - 2006


Dive into the research topics of 'River networks and watershed maps of triangulated terrains revisited'. Together they form a unique fingerprint.

Cite this