Implicit flow routing on terrains with applications to surface networks and drainage structures

M.T. Berg, de, H.J. Haverkort, K. Tsirogiannis

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

5 Citations (Scopus)
73 Downloads (Pure)

Abstract

Flow-related structures on terrains are defined in terms of paths of steepest descent (or ascent). A steepest descent path on a polyhedral terrain T with n vertices can have T(n^2) complexity. The watershed of a point p --- the set of points on T whose paths of steepest descent reach p --- can have complexity T(n^3). We present a technique for tracing a collection of n paths of steepest descent on T implicitly in O(n logn) time. We then derive O(n log n) time algorithms for: (i) computing for each local minimum p of T the triangles contained in the watershed of p and (ii) computing the surface network graph of T. We also present an O(n^2) time algorithm that computes the watershed area for each local minimum of T.
Original languageEnglish
Title of host publicationProceedings 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'11, San Francisco CA, USA, January 23-25, 2011)
EditorsD. Randall
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages285-296
ISBN (Print)978-089871993-2
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Implicit flow routing on terrains with applications to surface networks and drainage structures'. Together they form a unique fingerprint.

Cite this