MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 Fixed physically incorrect figure.

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 (not necessarily physically accurately) 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.

1

# The rain hull and the rain ridge

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 (not necessarily physically accurately) in this side-view schematic:

Perhaps the computation is NP-hard if $M$ is presented as a PL-manifold? TINs have special properties that might render the computation polynomial.

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.