Water retention on random surfaces
Water retention on random surfaces is the simulation of catching of water in ponds on a surface of cells of various heights on a regular array such as a square lattice, where water is rained down on every cell in the system. The boundaries of the system are open and allow water to flow out. Water will be trapped in ponds, and eventually all ponds will fill to their maximum height, with any additional water flowing over spillways and out the boundaries of the system. The problem is to find the amount of water trapped or retained for a given surface. This has been studied extensively for random surfaces.
Random surfaces
One system in which the retention question has been studied is a surface of random heights. Here one can map the random surface to site percolation, and each cell is mapped to a site on the underlying graph or lattice that represents the system. Using percolation theory, one can explain many properties of this system. It is an example of the invasion percolation model in which fluid is introduced in the system from any random site.[1][2][3]
In hydrology, one is concerned with runoff and formation of catchments.[4] The boundary between different drainage basin (watersheds in North America) forms a drainage divide with a fractal dimension of about 1.22.[5][6][7]
The retention problem can be mapped to standard percolation.[8][9][10] For a system of five equally probable levels, for example, the amount of water stored R5 is just the sum of the water stored in two-level systems R2(p) with varying fractions of levels p in the lowest state:
- R5 = R2(1/5) + R2(2/5) + R2(3/5) + R2(4/5)
Typical two-level systems 1,2 with p = 0.2, 0.4, 0.6, 0.8 are shown on the right (blue: wet, green: dry, yellow: spillways bordering wet sites). The net retention of a five-level system is the sum of all these. The top level traps no water because it is far above the percolation threshold for a square lattice, 0.592746.
The retention of a two-level system R2(p) is the amount of water connected to ponds that do not touch the boundary of the system. When p is above the critical percolation threshold p c, there will be a percolating cluster or pond that visits the entire system. The probability that a point belongs to the percolating or "infinite" cluster is written as P∞ in percolation theory, and it is related to R2(p) by R2(p)/L2 = p − P∞ where L is the size of the square. Thus, the retention of a multilevel system can be related to a well-known quantity in percolation theory.
To measure the retention, one can use a flooding algorithm in which water is introduced from the boundaries and floods through the lowest spillway as the level is raised. The retention is just the difference in the water level that a site was flooded minus the height of the terrain below it.
Besides the systems of discrete levels described above, one can make the terrain variable a continuous variable say from 0 to 1. Likewise, one can make the surface height itself be a continuous function of the spatial variables. In all cases, the basic concept of the mapping to an appropriate percolation system remains.
A curious result is that a square system of n discrete levels can retain more water than a system of n+1 levels, for sufficiently large order L > L*. This behavior can be understood through percolation theory, which can also be used to estimate L* ≈ (p − pc)−ν where ν = 4/3, p = i*/n where i* is the largest value of i for which i/n < pc, and pc = 0.592746 is the site percolation threshold for a square lattice. Numerical simulations give the following values of L*, which are extrapolated to non-integer values. For example, R2 < R3 for L ≤ 51, but R2 > R3 for L ≥ 52:[8]
| n | n + 1 | L* | Retention at L* |
|---|---|---|---|
| 2 | 3 | 51.12 | 790 |
| 4 | 5 | 198.1 | 26000 |
| 7 | 8 | 440.3 | 246300 |
| 9 | 10 | 559.1 | 502000 |
| 12 | 13 | 1390.6 | 428850 |
| 14 | 15 | 1016.3 | 2607000 |
As n gets larger, crossing become less and less frequent, and the value of L* where crossing occurs is no longer a monotonic function of n.
The retention when the surface is not entirely random but correlated with a Hurst exponent H is discussed in Schrenk et al.[10]
See also
References
- ↑ Chayes, J. T.; L. Chayes; C. M. Newman (1985). "The stochastic geometry of invasion percolation". Communications in Mathematical Physics 101 (3): 383–407. doi:10.1007/BF01216096. Bibcode: 1985CMaPh.101..383C. http://projecteuclid.org/euclid.cmp/1104114182.
- ↑ Damron, Michael; Artëm Sapozhnikov; Bálint Vágvölgyi (2009). "Relations between invasion percolation and critical percolation in two dimensions". Annals of Probability 37 (6): 2297–2331. doi:10.1214/09-AOP462.
- ↑ van den Berg, Jacob; Antal Járai; Bálint Vágvölgyi (2007). "The size of a pond in 2D invasion percolation". Electronic Communications in Probability 12: 411–420. doi:10.1214/ECP.v12-1327. Bibcode: 2007arXiv0708.4369V.
- ↑ Tetzlaff, D.; McDonnell, J. J.; Uhlenbrook, S.; McGuire, K. J.; Bogaart, P. W.; Naef, F.; Baird, A. J.; Dunn, S. M. et al. (2011). "Conceptualizing catchment processes: simply too complex?". Hydrological Processes 22 (11): 1727–1730. doi:10.1002/hyp.7069. Bibcode: 2008HyPr...22.1727T.
- ↑ Fehr, E.; D. Kadau; N. A. M. Araújo; J. S. Andrade Jr; H. J. Herrmann (2011). "Scaling Relations for Watersheds". Physical Review E 84 (3): 036116. doi:10.1103/PhysRevE.84.036116. PMID 22060465. Bibcode: 2011PhRvE..84c6116F.
- ↑ Schrenk, K. J.; N. A. M. Araújo; J. S. Andrade Jr; H. J. Herrmann (2012). "Fracturing Ranked Surfaces". Scientific Reports 2: 348. doi:10.1038/srep00348. PMID 22470841. Bibcode: 2012NatSR...2E.348S.
- ↑ Fehr, E.; D. Kadau; J. S. Andrade Jr; H. J. Herrmann (2011). "Impact of Perturbations on Watersheds". Physical Review Letters 106 (4): 048501. doi:10.1103/PhysRevLett.106.048501. PMID 21405368. Bibcode: 2011PhRvL.106d8501F.
- ↑ 8.0 8.1 Knecht, Craig; Walter Trump; Daniel ben-Avraham; Robert M. Ziff (2012). "Retention capacity of random surfaces". Physical Review Letters 108 (4): 045703. doi:10.1103/PhysRevLett.108.045703. PMID 22400865. Bibcode: 2012PhRvL.108d5703K. https://arxiv.org/trackback/1110.6166.
- ↑ Baek, Seung Ki; Beom Jun Kim (2012). "Critical Condition of the Water-Retention Model". Physical Review E 85 (3): 032103. doi:10.1103/PhysRevE.85.032103. PMID 22587136. Bibcode: 2012PhRvE..85c2103B.
- ↑ 10.0 10.1 Schrenk, K. J.; N. A. M Araújo; R. M. Ziff; H. J. Herrmann (2014). "Retention capacity of correlated surfaces". Physical Review E 89 (6): 062141. doi:10.1103/PhysRevE.89.062141. PMID 25019758. Bibcode: 2014PhRvE..89f2141S.
Further reading
- Pickover, Clifford (2002). The Zen of Magic Squares, Circles, and Stars: An Exhibition of Surprising Structures Across Dimensions. Princeton, NJ: Princeton University Press. ISBN 978-0-691-11597-9.
- Stauffer, Dietrich; Aharony, A. (1994). Introduction to Percolation Theory. London Bristol, PA: Taylor & Francis. ISBN 978-0-7484-0253-3.
External links
- https://commons.wikimedia.org/wiki/Category:Associative_magic_squares_of_order_4
- Hugo Pfoertner. OEIS sequence A201126 (Maximum water retention of a magic square of order n), with links to magic square pictures
- Hugo Pfoertner. OEIS sequence A201127 (Maximum water retention of a semi-magic square of order n)
- Discussion site for Al Zimmermann's Programming Contests
- Item on Futility Closet
- OEIS sequence A261798 (Maximum water retention of an associative magic square of order n)
- OEIS sequence A268311 (Number of free polyominoes that form a continuous path of edge joined cells spanning an n X n square in both dimensions)—Polyominoe enumeration and lake patterns
- OEIS sequence A275359 (Maximum incarceration of numbers in an n X n X n number cubes with full incarceration volumes)—Upgrade the model from 2D to 3D
- [1] Nature 2018
- [2] Water retention histogram as a computing problem
- http://oeis.org/A331507/ Maximum number of ponds
 |  |
