View article

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model\emph {braided rivers}(multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a\emph {sand function} that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are -different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum -different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.