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
<a href="http://en.wikipedia.org/wiki/Triangulated_irregular_network">triangulated irregular network (TIN)</a>.
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
<a href="http://mathoverflow.net/questions/39378/">this MO question</a>.
<b>Q1.</b>
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:
<b>Update</b> (<em>13Aug11</em>): I have corrected the figure to more accurately reflect
physical reality. Thanks to [Oswin Aicholzer][1] for setting me straight.
<br />
<img src="http://cs.smith.edu/~orourke/MathOverflow/RainColumn.jpg" alt="RainColumn" />
<br />
Perhaps the computation is NP-hard if $M$ is presented as a PL-manifold? TINs have special properties that might
render the computation polynomial.
<b>Update</b>.
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
<a href="http://eurocg11.inf.ethz.ch/abstracts/60.pdf">"Implicit Flow Routing on Triangulated Terrains"
by deBerg et al.</a>)
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][2], 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
<a href="http://mathoverflow.net/questions/48716/">this inadequately
answered MO question</a> (inadequately answered by me).
<b>Q2.</b>
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:
<b>Q3.</b>
Can an extended metric be assigned to $\overline{M}$ so that its
geodesics are its trickle paths?
An
<a href="http://en.wikipedia.org/wiki/Metric_%28mathematics%29#Extended_metrics">extended metric</a>
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.
[1]: http://www.ist.tugraz.at/oaich/
[2]: http://en.wikipedia.org/wiki/Cut_locus