Continuum percolation theory

<h2 id="early-history">Early history</h2>
In the early 1960s <a href="/facts/Edgar_Gilbert/r6g0Tlun">Edgar Gilbert</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> proposed a mathematical model in wireless networks that gave rise to the field of continuum percolation theory, thus generalizing discrete percolation.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> The underlying points of this model, sometimes known as the Gilbert disk model, were scattered uniformly in the infinite plane ℝ2 according to a homogeneous <a href="/facts/Poisson_process/8uphjAUc">Poisson process</a>. Gilbert, who had noticed similarities between discrete and continuum percolation,<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> then used concepts and techniques from the probability subject of <a href="/facts/Branching_processes/JzdGdWrQ">branching processes</a> to show that a <a href="/facts/Percolation_threshold/z67jYyyF">threshold value</a> existed for the infinite or "giant" component.

<h2 id="definitions-and-terminology">Definitions and terminology</h2>
The exact names, terminology, and definitions of these models may vary slightly depending on the source, which is also reflected in the use of <a href="/facts/Point_process_notation/WsgC72t7">point process notation</a>.

<h3>Common models</h3>
A number of well-studied models exist in continuum percolation, which are often based on homogeneous <a href="/facts/Poisson_point_process/8uphjAUc">Poisson point processes</a>.

<h4>Disk model</h4>
Consider a collection of points {xi} in the plane ℝ2 that form a homogeneous Poisson process Φ with constant (point) density λ. For each point of the Poisson process (i.e. xi ∈ Φ), place a disk Di with its center located at the point xi. If each disk Di has a random radius Ri (from a common <a href="/facts/Probability_distribution/EpsKKVRu">distribution</a>) that is <a href="/facts/Independence_(probability_theory)/NUzQtnUL">independent</a> of all the other radii and all the underlying points {xi}, then the resulting mathematical structure is known as a random disk model.

<h4>Boolean model</h4>
Given a random disk model, if the set union of all the disks {Di} is taken, then the resulting structure ⋃i Di is known as a Boolean–Poisson model (also known as simply the <a href="/facts/Boolean_model_(probability_theory)/qdgQxDx8">Boolean model</a>),<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> which is a commonly studied model in continuum percolation<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> as well as <a href="/facts/Stochastic_geometry/r7BW9A8k">stochastic geometry</a>.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> If all the radii are set to some common constant, say, r > 0, then the resulting model is sometimes known as the Gilbert disk (Boolean) model.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h4>Germ-grain model</h4>
The disk model can be generalized to more arbitrary shapes where, instead of a disk, a random <a href="/facts/Compact_space/d0cgXJH7">compact</a> (hence bounded and closed in ℝ2) shape Si is placed on each point xi. Again, each shape Si has a common <a href="/facts/Probability_distribution/EpsKKVRu">distribution</a> and <a href="/facts/Independence_(probability_theory)/NUzQtnUL">independent</a> to all other shapes and the underlying (Poisson) point process. This model is known as the germ–grain model where the underlying points {xi} are the germs and the random compact shapes Si are the grains. The <a href="/facts/Set_union/KVVXKfWl">set union</a> of all the shapes forms a Boolean germ-grain model. Typical choices for the grains include disks, random <a href="/facts/Polygon/xvkmYhvG">polygon</a> and segments of random length.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
Boolean models are also examples of <a href="/facts/Stochastic_processes/Ng1n1dnB">stochastic processes</a> known as coverage processes.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> The above models can be extended from the plane ℝ2 to general Euclidean space ℝn.

<h3>Components and criticality</h3>
In the Boolean–Poisson model, disks there can be isolated groups or clumps of disks that do not contact any other clumps of disks. These clumps are known as components. If the area (or volume in higher dimensions) of a component is infinite, one says it is an infinite or "giant" component. A major focus of percolation theory is establishing the conditions when giant components exist in models, which has parallels with the study of random networks. If no big component exists, the model is said to be subcritical. The conditions of giant component criticality naturally depend on parameters of the model such as the density of the underlying point process.

<h2 id="excluded-area-theory">Excluded area theory</h2>
The excluded area of a placed object is defined as the minimal area around the object into which an additional object cannot be placed without overlapping with the first object. For example, in a system of randomly oriented homogeneous rectangles of length l, width w and aspect ratio r = ⁠l/w⁠, the average excluded area is given by:<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

A
          
            r
          
        
        =
        2
        l
        w
        
          (
          
            1
            +
            
              
                4
                
                  π
                  
                    2
                  
                
              
            
          
          )
        
        +
        
          
            2
            π
          
        
        
          (
          
            
              l
              
                2
              
            
            +
            
              w
              
                2
              
            
          
          )
        
        =
        2
        
          l
          
            2
          
        
        
          [
          
            
              
                1
                r
              
            
            
              (
              
                1
                +
                
                  
                    4
                    
                      π
                      
                        2
                      
                    
                  
                
              
              )
            
            +
            
              
                1
                π
              
            
            
              (
              
                1
                +
                
                  
                    1
                    
                      r
                      
                        2
                      
                    
                  
                
              
              )
            
          
          ]
        
      
    
    {\displaystyle A_{r}=2lw\left(1+{\frac {4}{\pi ^{2}}}\right)+{\frac {2}{\pi }}\left(l^{2}+w^{2}\right)=2l^{2}\left[{\frac {1}{r}}\left(1+{\frac {4}{\pi ^{2}}}\right)+{\frac {1}{\pi }}\left(1+{\frac {1}{r^{2}}}\right)\right]}

In a system of identical ellipses with semi-axes a and b and ratio r = ⁠a/b⁠, and perimeter C, the average excluded areas is given by:<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

A
          
            r
          
        
        =
        2
        π
        a
        b
        +
        
          
            
              C
              
                2
              
            
            
              2
              π
            
          
        
      
    
    {\displaystyle A_{r}=2\pi ab+{\frac {C^{2}}{2\pi }}}

The excluded area theory states that the critical number density (percolation threshold) Nc of a system is inversely proportional to the average excluded area Ar:

N
          
            
              c
            
          
        
        ∝
        
          A
          
            r
          
          
            −
            1
          
        
      
    
    {\displaystyle N_{\mathrm {c} }\propto A_{r}^{-1}}

It has been shown via Monte-Carlo simulations that percolation threshold in both homogeneous and heterogeneous systems of rectangles or ellipses is dominated by the average excluded areas and can be approximated fairly well by the linear relation

N
          
            
              c
            
          
        
        −
        
          N
          
            
              c
            
            0
          
        
        ∝
        
          A
          
            r
          
          
            −
            1
          
        
      
    
    {\displaystyle N_{\mathrm {c} }-N_{\mathrm {c} 0}\propto A_{r}^{-1}}

with a proportionality constant in the range 3.1–3.5.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a><a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

<h2 id="applications">Applications</h2>

The applications of percolation theory are various and range from material sciences to <a href="/facts/Wireless_communication/GfDoFwfo">wireless communication</a> systems. Often the work involves showing that a type of <a href="/facts/Phase_transition/eLP2BY8R">phase transition</a> occurs in the system.

<h3>Wireless networks</h3>
Wireless networks are sometimes best represented with stochastic models owing to their complexity and unpredictability, hence continuum percolation have been used to develop <a href="/facts/Stochastic_geometry_models_of_wireless_networks/4RWr4aA1">stochastic geometry models of wireless networks</a>. For example, the tools of continuous percolation theory and coverage processes have been used to study the coverage and connectivity of <a href="/facts/Sensor_network/r5LIAVsU">sensor networks</a>.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a><a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> One of the main limitations of these networks is energy consumption where usually each node has a battery and an embedded form of energy harvesting. To reduce energy consumption in sensor networks, various sleep schemes have been suggested that entail having a subcollection of nodes go into a low energy-consuming sleep mode. These sleep schemes obviously affect the coverage and connectivity of sensor networks. Simple power-saving models have been proposed such as the simple uncoordinated 'blinking' model where (at each time interval) each node independently powers down (or up) with some fixed probability. Using the tools of percolation theory, a blinking Boolean Poisson model has been analyzed to study the <a href="/facts/Latency_(engineering)/6Bjhn30H">latency</a> and connectivity effects of such a simple power scheme.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Stochastic_geometry_models_of_wireless_networks/4RWr4aA1">Stochastic geometry models of wireless networks</a></li>
<li><a href="/facts/Random_graphs/gfQhq1Sz">Random graphs</a></li>
<li><a href="/facts/Boolean_model_(probability_theory)/qdgQxDx8">Boolean model (probability theory)</a></li>
<li><a href="/facts/Percolation_thresholds/z67jYyyF">Percolation thresholds</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Meester, R. (1996). Continuum Percolation. Vol. 119. Cambridge University Press.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Franceschetti, M.; Meester, R. (2007). Random Networks for Communication: From Statistical Physics to Information Systems. Vol. 24. Cambridge University Press.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Franceschetti, M.; Meester, R. (2007). Random Networks for Communication: From Statistical Physics to Information Systems. Vol. 24. Cambridge University Press.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Gilbert, E. N. (1961). "Random plane networks". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 533–543. doi:10.1137/0109045. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Dousse, O.; Baccelli, F.; Thiran, P. (2005). "Impact of interferences on connectivity in ad hoc networks". IEEE/ACM Transactions on Networking. 13 (2): 425–436. CiteSeerX 10.1.1.5.3971. doi:10.1109/tnet.2005.845546. S2CID 1514941. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Dousse, O.; Franceschetti, M.; Macris, N.; Meester, R.; Thiran, P. (2006). "Percolation in the signal to interference ratio graph". Journal of Applied Probability. 2006 (2): 552–562. doi:10.1239/jap/1152413741. <a href="https://doi.org/10.1239%2Fjap%2F1152413741" target="_blank">https://doi.org/10.1239%2Fjap%2F1152413741</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Balberg, I. (1987). "Recent developments in continuum percolation". Philosophical Magazine B. 56 (6): 991–1003. Bibcode:1987PMagB..56..991B. doi:10.1080/13642818708215336. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Gilbert, E. N. (1961). "Random plane networks". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 533–543. doi:10.1137/0109045. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Franceschetti, M.; Meester, R. (2007). Random Networks for Communication: From Statistical Physics to Information Systems. Vol. 24. Cambridge University Press.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Hall, P. (1985). "On continuum percolation". The Annals of Probability. 13 (4): 1250–1266. doi:10.1214/aop/1176992809. <a href="https://doi.org/10.1214%2Faop%2F1176992809" target="_blank">https://doi.org/10.1214%2Faop%2F1176992809</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Stoyan, D.; Kendall, W. S.; Mecke, J.; Ruschendorf, L. (1995). Stochastic Geometry and Its Applications. Vol. 2. Wiley Chichester.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Meester, R. (1996). Continuum Percolation. Vol. 119. Cambridge University Press.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Stoyan, D.; Kendall, W. S.; Mecke, J.; Ruschendorf, L. (1995). Stochastic Geometry and Its Applications. Vol. 2. Wiley Chichester.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Balister, Paul; Sarkar, Amites; Bollobás, Béla (2008). "Percolation, connectivity, coverage and colouring of random geometric graphs". Handbook of Large-Scale Random Networks. pp. 117–142.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Stoyan, D.; Kendall, W. S.; Mecke, J.; Ruschendorf, L. (1995). Stochastic Geometry and Its Applications. Vol. 2. Wiley Chichester.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Hall, P. (1988). Introduction to the theory of coverage processes. Vol. 1. New York: Wiley.[ISBN missing] <a href="/wiki/Wikipedia:Citing_sources" target="_blank">/wiki/Wikipedia:Citing_sources</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Li, Jiantong; Östling, Mikael (2013). "Percolation thresholds of two-dimensional continuum systems of rectangles". Physical Review E. 88 (1): 012101. Bibcode:2013PhRvE..88a2101L. doi:10.1103/PhysRevE.88.012101. ISSN 1539-3755. PMID 23944408. S2CID 21438506. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Li, Jiantong; Östling, Mikael (2016). "Precise percolation thresholds of two-dimensional random systems comprising overlapping ellipses". Physica A: Statistical Mechanics and Its Applications. 462: 940–950. Bibcode:2016PhyA..462..940L. doi:10.1016/j.physa.2016.06.020. ISSN 0378-4371. <a href="http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-193152" target="_blank">http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-193152</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Li, Jiantong; Östling, Mikael (2013). "Percolation thresholds of two-dimensional continuum systems of rectangles". Physical Review E. 88 (1): 012101. Bibcode:2013PhRvE..88a2101L. doi:10.1103/PhysRevE.88.012101. ISSN 1539-3755. PMID 23944408. S2CID 21438506. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Li, Jiantong; Östling, Mikael (2016). "Precise percolation thresholds of two-dimensional random systems comprising overlapping ellipses". Physica A: Statistical Mechanics and Its Applications. 462: 940–950. Bibcode:2016PhyA..462..940L. doi:10.1016/j.physa.2016.06.020. ISSN 0378-4371. <a href="http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-193152" target="_blank">http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-193152</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Dousse, O.; Mannersalo, P.; Thiran, P. (2004). "Latency of wireless sensor networks with uncoordinated power saving mechanisms". Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM. pp. 109–120. <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Gui, C.; Mohapatra, P. (2004). "Power conservation and quality of surveillance in target tracking sensor networks". Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. ACM. pp. 129–143. <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Dousse, O.; Mannersalo, P.; Thiran, P. (2004). "Latency of wireless sensor networks with uncoordinated power saving mechanisms". Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM. pp. 109–120. <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
</ol>

Continuum percolation theory open-in-new

Continuum percolation theory