HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
probability theory Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...
, continuum percolation theory is a branch of mathematics that extends discrete
percolation theory In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...
to continuous space (often
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
). More specifically, the underlying points of discrete percolation form types of lattices whereas the underlying points of continuum percolation are often randomly positioned in some continuous space and form a type of
point process In statistics and probability theory, a point process or point field is a set of a random number of mathematical points randomly located on a mathematical space such as the real line or Euclidean space. Kallenberg, O. (1986). ''Random Measures'', ...
. For each point, a random shape is frequently placed on it and the shapes overlap each with other to form clumps or components. As in discrete percolation, a common research focus of continuum percolation is studying the conditions of occurrence for infinite or giant components. Other shared concepts and analysis techniques exist in these two types of percolation theory as well as the study of
random graphs In mathematics, random graph is the general term to refer to probability distributions over Graph (discrete mathematics), graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. ...
and random geometric graphs. Continuum percolation arose from an early mathematical model for
wireless networks A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking allows homes, telecommunications networks, and business installations to avoid the costly process of introducing cables in ...
, which, with the rise of several wireless network technologies in recent years, has been generalized and studied in order to determine the theoretical bounds of information capacity and performance in wireless networks. In addition to this setting, continuum percolation has gained application in other disciplines including biology, geology, and physics, such as the study of porous material and
semiconductor A semiconductor is a material with electrical conductivity between that of a conductor and an insulator. Its conductivity can be modified by adding impurities (" doping") to its crystal structure. When two regions with different doping level ...
s, while becoming a subject of mathematical interest in its own right.


Early history

In the early 1960s Edgar Gilbert proposed a mathematical model in wireless networks that gave rise to the field of continuum percolation theory, thus generalizing discrete percolation. The underlying points of this model, sometimes known as the Gilbert disk model, were scattered uniformly in the infinite plane according to a homogeneous
Poisson process In probability theory, statistics and related fields, a Poisson point process (also known as: Poisson random measure, Poisson random point field and Poisson point field) is a type of mathematical object that consists of Point (geometry), points ...
. Gilbert, who had noticed similarities between discrete and continuum percolation, then used concepts and techniques from the probability subject of branching processes to show that a threshold value existed for the infinite or "giant" component.


Definitions and terminology

The exact names, terminology, and definitions of these models may vary slightly depending on the source, which is also reflected in the use of point process notation.


Common models

A number of well-studied models exist in continuum percolation, which are often based on homogeneous
Poisson point process In probability theory, statistics and related fields, a Poisson point process (also known as: Poisson random measure, Poisson random point field and Poisson point field) is a type of mathematical object that consists of points randomly located ...
es.


Disk model

Consider a collection of points in the plane that form a homogeneous Poisson process with constant (point) density . For each point of the Poisson process (i.e. ), place a disk with its center located at the point . If each disk has a random radius (from a common
distribution Distribution may refer to: Mathematics *Distribution (mathematics), generalized functions used to formulate solutions of partial differential equations *Probability distribution, the probability of a particular value or value range of a varia ...
) that is
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in Pennsylvania, United States * Independentes (English: Independents), a Portuguese artist ...
of all the other radii and all the underlying points , then the resulting mathematical structure is known as a random disk model.


Boolean model

Given a random disk model, if the set union of all the disks is taken, then the resulting structure is known as a Boolean–Poisson model (also known as simply the
Boolean model Any kind of logic, function, expression, or theory based on the work of George Boole is considered Boolean. Related to this, "Boolean" may refer to: * Boolean data type, a form of data with only two possible values (usually "true" and "false" ...
), which is a commonly studied model in continuum percolation as well as
stochastic geometry In mathematics, stochastic geometry is the study of random spatial patterns. At the heart of the subject lies the study of random point patterns. This leads to the theory of spatial point processes, hence notions of Palm conditioning, which exten ...
. If all the radii are set to some common constant, say, , then the resulting model is sometimes known as the Gilbert disk (Boolean) model.


Germ-grain model

The disk model can be generalized to more arbitrary shapes where, instead of a disk, a random
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...
(hence bounded and closed in ) shape is placed on each point . Again, each shape has a common
distribution Distribution may refer to: Mathematics *Distribution (mathematics), generalized functions used to formulate solutions of partial differential equations *Probability distribution, the probability of a particular value or value range of a varia ...
and
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in Pennsylvania, United States * Independentes (English: Independents), a Portuguese artist ...
to all other shapes and the underlying (Poisson) point process. This model is known as the germ–grain model where the underlying points are the ''germs'' and the random compact shapes are the ''grains''. The
set union In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other. A refers to a union of ze ...
of all the shapes forms a Boolean germ-grain model. Typical choices for the grains include disks, random
polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
and segments of random length. Boolean models are also examples of
stochastic processes In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables in a probability space, where the index of the family often has the interpretation of time. Stoc ...
known as coverage processes. The above models can be extended from the plane to general Euclidean space .


Components and criticality

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.


Excluded area theory

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 , width and aspect ratio , the average excluded area is given by: : A_r = 2lw\left(1 + \frac\right) + \frac\left(l^2 + w^2\right) = 2l^2\left \frac\left(1 + \frac\right) + \frac\left(1 + \frac\right) \right In a system of identical ellipses with semi-axes and and ratio , and perimeter , the average excluded areas is given by: :A_r = 2\pi ab + \frac The excluded area theory states that the critical number density (percolation threshold) of a system is inversely proportional to the average excluded area : :N_\mathrm \propto A_r^ 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_\mathrm - N_ \propto A_r^ with a proportionality constant in the range 3.1–3.5.


Applications

The applications of percolation theory are various and range from material sciences to
wireless communication Wireless communication (or just wireless, when the context allows) is the transfer of information (''telecommunication'') between two or more points without the use of an electrical conductor, optical fiber or other continuous guided med ...
systems. Often the work involves showing that a type of
phase transition In physics, chemistry, and other related fields like biology, a phase transition (or phase change) is the physical process of transition between one state of a medium and another. Commonly the term is used to refer to changes among the basic Sta ...
occurs in the system.


Wireless networks

Wireless networks are sometimes best represented with stochastic models owing to their complexity and unpredictability, hence continuum percolation have been used to develop stochastic geometry models of wireless networks. For example, the tools of continuous percolation theory and coverage processes have been used to study the coverage and connectivity of
sensor network Wireless sensor networks (WSNs) refer to networks of spatially dispersed and dedicated sensors that monitor and record the physical conditions of the environment and forward the collected data to a central location. WSNs can measure environmental ...
s. 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 latency and connectivity effects of such a simple power scheme.


See also

* Stochastic geometry models of wireless networks *
Random graphs In mathematics, random graph is the general term to refer to probability distributions over Graph (discrete mathematics), graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. ...
*
Boolean model (probability theory) For statistics in probability theory, the Boolean-Poisson model or simply Boolean model for a random subset of the plane (or higher dimensions, analogously) is one of the simplest and most tractable models in stochastic geometry. Take a Poisson ...
* Percolation thresholds


References

{{Stochastic processes Percolation theory Probability theory Phase transitions