Name
Title | ||
|---|---|---|
Implicit flow routing on terrains with applications to surface networks and drainage structures |
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 θ(n2) complexity. The watershed of a point p---the set of points on T whose paths of steepest descent reach p---can have complexity θ(n3). We present a technique for tracing a collection of n paths of steepest descent on T implicitly in O(n log n) 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(n2) time algorithm that computes the watershed area for each local minimum of T. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2133036.2133060 | SODA |
Keywords | Field | DocType |
n path,steepest descent reach p,n vertex,derive o,local minimum p,steepest descent,drainage structure,n log n,time algorithm,implicit flow routing,steepest descent path,point p | Discrete mathematics,Gradient descent,Combinatorics,Vertex (geometry),Terrain,Watershed,Flow routing,Polyhedral terrain,Time complexity,Tracing,Mathematics | Conference |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 3 | 0.47 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark De Berg | 1 | 1497 | 153.24 |
| Herman Haverkort | 2 | 244 | 17.68 |
| Constantinos Tsirogiannis | 3 | 12 | 5.93 |