The Maximum Volume of Trapped Rain Water in 3D

Question

A classic algorithm question in 2D version is typically described as

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given the input

[0,1,0,2,1,0,1,3,2,1,2,1]  

the return value would be

6 

The algorithm that I used to solve the above 2D problem is

int trapWaterVolume2D(vector<int> A) {     int n = A.size();     vector<int> leftmost(n, 0), rightmost(n, 0);      //left exclusive scan, O(n), the highest bar to the left each point     int leftMaxSoFar = 0;     for (int i = 0; i < n; i++){         leftmost[i] = leftMaxSoFar;         if (A[i] > leftMaxSoFar) leftMaxSoFar = A[i];     }       //right exclusive scan, O(n), the highest bar to the right each point     int rightMaxSoFar = 0;     for (int i = n - 1; i >= 0; i--){         rightmost[i] = rightMaxSoFar;         if (A[i] > rightMaxSoFar) rightMaxSoFar = A[i];     }      // Summation, O(n)     int vol = 0;     for (int i = 0; i < n; i++){         vol += max(0, min(leftmost[i], rightmost[i]) - A[i]);     }     return vol; } 

My Question is how to make the above algorithm extensible to the 3D version of the problem, to compute the maximum of water trapped in real-world 3D terrain. i.e. To implement

int trapWaterVolume3D(vector<vector<int> > A); 

Sample graph:

We know the elevation at each (x, y) point and the goal is to compute the maximum volume of water that can be trapped in the shape. Any thoughts and references are welcome.

Answer 1

For each point on the terrain consider all paths from that point to the border of the terrain. The level of water would be the minimum of the maximum heights of the points of those paths. To find it we need to perform a slightly modified Dijkstra's algorithm, filling the water level matrix starting from the border.

For every point on the border set the water level to the point height For every point not on the border set the water level to infinity Put every point on the border into the set of active points While the set of active points is not empty:     Select the active point P with minimum level     Remove P from the set of active points     For every point Q adjacent to P:         Level(Q) = max(Height(Q), min(Level(Q), Level(P)))         If Level(Q) was changed:             Add Q to the set of active points