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.
|Title of host publication||Abstracts 22nd European Workshop on Computational Geometry (EWCG 2006, Delphi, Greece, March 27-29, 2006)|
|Editors||I. Emiris, M. Karavelas, L. Palios|
|Publication status||Published - 2006|