The rain hull and the rain ridge

Question

Rain falls steadily on an island, a 2-manifold $M$, which you may assume, as you prefer, is: (a) smooth, or (b) a PL-manifold, or perhaps even (c) a triangulated irregular network (TIN). After a time, $M$ is saturated, in the sense that every raindrop drains into the ocean rather than filling yet-unfilled crevices or basins. At this point, we have what I will dub the rain hull of $M$, $H_R(M)$, a uni-directional version of the the reflex-free hull, explored (by Bill Thurston) in this MO question.

Q1. How difficult is to compute the rain hull $H_R(M)$?

My sense is that it might be quite difficult, because it seems there can be nonlocal influences, as crudely depicted in this side-view schematic: Update (13Aug11): I have corrected the figure to more accurately reflect physical reality. Thanks to Oswin Aicholzer for setting me straight.
                      
Perhaps the computation is NP-hard if $M$ is presented as a PL-manifold? TINs have special properties that might render the computation polynomial. Update. Joel Hamkins has convincingly argued (see below) that the computation is polynomial-time.

Let us assume we have $\overline{M} = H_R(M)$ computed or given. A raindrop falling on $p \in \overline{M}$ might follow a unique trickle path (that is the technical term: e.g., see "Implicit Flow Routing on Triangulated Terrains" by deBerg et al.) to the ocean, or the drop may randomly 'fracture' to follow distinct paths to the ocean. Define the rain ridge (my terminology) $R(\overline{M})$ to be the complement of the points of $\overline{M}$ that have a unique trickle path.

So points on the rain ridge are akin to points on a cut locus, in that they have two or more distinct paths to $\partial \overline{M}$. They are, in a sense, continental-divide points, a topic explored in this inadequately answered MO question (inadequately answered by me).

Q2. What can be said about the structure of the rain ridge $R(\overline{M})$?

Unlike the cut locus, it is not always a tree. All the points in a filled basin are in the rain ridge, for when a raindrop lands in a filled basin, it is natural to assume it "spreads out" and spills in equal portions over every boundary point of the basin. But surely there are substantive properties to investigate. Surely the rain ridge $R(\overline{M})$ cannot be an arbitrary subset of $\overline{M}$?

I finally come to my main question, which I fear has a negative answer:

Q3. Can an extended metric be assigned to $\overline{M}$ so that its geodesics are its trickle paths?

An extended metric is one that permits $d(x,y) = \infty$ (e.g., for points not on the same trickle path). What I am hoping for here is a way to view the rain ridge as a cut locus of $\partial \overline{M}$, and then apply a century of knowledge on the cut locus to the rain ridge.

Partly baked ideas, subquestion observations, and random literature pointers all welcomed! My sense is that the considerable applied-math literature on watersheds has not approached these questions in their full mathematical generality, leaving room for delightful theorems.

Answer 1

Since you've explicitly welcomed half-baked ideas...

Regarding question 1, can't we just simulate the rain in polynomial time?

I am thinking of the same-connected-component problem in graph theory. Given two nodes $p$ and $q$ in a graph, we determine whether they are in the same component as follows: color $p$ blue, and then make passes through the graph, coloring blue any node that is directly connected to an already-blue node. Repeat until no new blue nodes arise, and then the component of $p$ consists precisely of the blue nodes. This takes polynomial time in the number of vertices, since the number of passes is bounded by the number of vertices.

In your case, if we imagine a discrete version of the picture, with tiny finite elements and the edge resolution size $n$, that is, an $n\times n\times n$ cube, then can't we simply simulate the rain until the rain hull is saturated? We can follow a single drop along its trickle path, which always has a downward (or at worst horizontal) component by gravity. The complication, as your diagram suggests, are the non-local effects of rain filling up a basin which overspills a border far away, but it seems that this overspill can still be computed in polynomial time. That is, when a drop is added to a local pool, then we allow it to flow horizontally as much as it likes, and we allow it also to flow to nodes at the same altitude, provided there is a blue path from its current location to the new location. Since there are only $n^3$ locations altogether, we can determine whether it is collected or shed in polynomial time.

And if the trickle path of a single rain drop can be computed in polynomial time of $n$, then we simply repeat the process of adding raindrops, from each of the $n^2$ sources overhead, until no new drops are added permanently to the rain hull. Since we can collect at most $n^3$ drops of rain altogether, we get a polynomial bound on the number of simulated raindrops we need to consider. And therefore in the end we can compute the rain hull in polynomial time of $n$.

(Perhaps you will object that your intended input will be much smaller than $n$.)