Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.
                       RainColumn
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.

share|improve this question
6  
This is my 100th MO question :-) –  Joseph O'Rourke Jul 10 '11 at 22:36
    
Can we assume M and/or Mbar pass the z-axis test? I.e. is M= f(x,y) for some function f and coordinatization of the ocean containing the island? If so, maybe topographers have the answer. Gerhard "Email Me About System Design" Paseman, 2011.07.10 –  Gerhard Paseman Jul 10 '11 at 23:31
    
@Gehard: That is the TIN assumption of GIS researchers. It seems more mathematically interesting to assume full generality, and to specialize to terrains (as they call them) if necesary. –  Joseph O'Rourke Jul 10 '11 at 23:43
    
I can imagine an iterative solution to calculate Mbar for those portions of the island which satisfy the TIN assumption, and do an approximation for the rest. However, I am still mulling over your picture above. Perhaps one can calculate mhat easily, where mhat is the result of pretending TIN holds, and then prove that Mbar differs on a set of sufficiently small measure. Another approach is to run the rain backwards, to capture essential aspects of the rain hull. Gerhard "Wild Guesses Are Our Specialty" Paseman, 2011.07.10 –  Gerhard Paseman Jul 11 '11 at 1:07
1  
A little celebration of the occasion is here: gilkalai.wordpress.com/2011/07/12/joes-100th-mo-question –  Gil Kalai Jul 13 '11 at 18:54
show 3 more comments

1 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$.)

share|improve this answer
    
I believe you are correct, Joel! I had thought perhaps some logic gadgets could be constructed, which would be a first step toward a 3SAT proof, but I no longer think such gates are possible. I think the issue with $n$ can be resolved. –  Joseph O'Rourke Jul 11 '11 at 17:34
    
Perhaps you could get computation if you allowed some kind of fluid friction in tiny tubes, which enabled pressure to build up, eventually exceeding a threshold that would then lead to siphon effects draining out large reservoirs. Or perhaps if you add capillary effects. I can imagine building switches that way. But without that kind of thing, it seems that the current formulation is monotone enough (we only add more blue pixels in the simulation) to allow the simulation to succeed. –  Joel David Hamkins Jul 11 '11 at 18:00
    
Yes, exactly, Joel, you've nailed it: I had falsely imagined a certain dynamism which is not present in the static "rain hull." –  Joseph O'Rourke Jul 11 '11 at 21:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.