
Nir Yefet 1998
project summary:


3D Visualization of percolation clusters
N. Yefet, as a project handed to Dr. J. Adler
Technion  The Israeli Institute of Technology
Many phenomena in physics, chemistry, and biology can be modeled
by spatial random processes.
Introduction
In this project the problem of PERCOLATION is investigated .
In order to introduce the concept of percolation in 3D we consider
an example from simple electricity.
Consider a large box, balls and a kid. Some balls are conductors and
some are not. The box's lower face is connected to an electrical contact.
The kid had came and started to throw the balls into the box. (As we know,
A kid doesn't recognize the difference among the balls). This kid is(was)
not a lazy one. He filled the box. Surprisingly, he chose to touch the
ball on top of the box. Is this kid still alive???
Most of the time we use the percolation model for which analytical
results are not available as in our example. Percolation can be easily
studied using more computer power than is available. In this project I
emphasis the need to use computers carefully, rather than as sledge hammers.
TOP
Percolation
Considering our simple physics problem into a specific mathematical model:
site
percolation on a box lattice. This uses an L x L x L box matrix
of 1s and 0s, called the site matrix. Each site is a ball. A 1
represents an `occupied` site (a conductor ball) and a 0
an `empty` site (a plastic ball). The sites are occupied randomly with
some site occupation probability, p.
A cluster is a set of occupied sites all of which are connected
to an occupied site by neighboring occupied sites. (Neighbors are only
in the x , y and zdirections, not along diagonals), i.e. an occupied
site belongs to a cluster if a member of the cluster is either above, below,
left or right of it. A spanning cluster has an element in both the
top and bottom surfaces of the site matrix. There is a certain probability
p to have a site be occupied.
As p increases, the probability that there is a cluster from one side
of the system to the opposite side increases. As the size of the square
lattice increases, there is a narrower range of p values for which we go
from no "spanning cluster" to the existence of a spanning cluster. This
is an example of a phase transition and many of the ideas that apply to
this simple model are also important for critical phenomena that are studied
in condensed matter physics and quantum field theory.
A 2D Site Percolation
[1]

3D Box filled with some clusters

TOP
The Critical Point
Investigations lead the result of how the probability
of a site matrix having a spanning cluster depends on the site occupation
probability p. Site percolation is an example of a critical phenomenon.
There is a special value of p, called the critical site occupation probability
p_{c},
such that for p < p_{c} spanning clusters never occur. While
for p p_{c} they always occur. The case p=p_{c} is called
a critical point.
TOP
HoshenKopelman Algorithm
HoshenKopelman algorithm describes the idea behind the percolation
check. The algorithm is based in labeling each occupied site in the crystal.
The algorithm can best be described by an example. Consider
a crystal with the following configuration.
xy0


xy1


xy2


xy3


5

4


6


4


11



4

4

4




4


16


4



9



10



13

10

15




1


3

2


8






12


8


4

1

1


2

1


7

2

1


2



14



Each place in the matrix is a site in the crystal. It's
a 3D matrix for simulation of a 3D crystal.
Assigning cluster labels to sites beginning at lower left
corner (0,0,0) and continues in the xdirection from left to right.
Each occupied site, located at (x,y,z) looks at its neighbors
sites with lowers coordinates (x,y,z1), (x,y1,z),(x1,y,z). Else neighbors
are unoccupied it gets the next available cluster label {i.e.
(3,0,0) is assigned 2} ELSE the site is assigned its label.
One can see that there might be different labels for the
same cluster as seen at sites (2,1,0) labeled 3 & site (3,1,0) labeled
2.
Let's see how did they get their labels?
Site (2,1,0) is assigned 3 because its neighbors are
unoccupied {NOTE that sites (3,1,0) hasn't get a label yet}
Site (3,1,0) is assigned label 2 because it has an occupied
neighbor at (3,1,1) labeled 2.
Noticing the linkage between the clusters and the improper
labels we set np(3)=2 which means that from now, we cancel the use of label
3 and use label 2 instead of it.
Using this method we assign the following proper labels
(3,1,1)
np(3)=2; (1,3,1) np(5)=4; (3,0,1) np(7)=2; (0,3,1) np(9)=4;
There are bit more complicated situations. At site (3,2,2)
np(12)=np(13)=10; than np(11)=4. At site (2,3,2) we set np(13)=4
and
update
np(12)=np(10)=4.
The
update of label13's neighbors is done in the first step of the labeling
loop in the algorithm using the original HoshenKopelman algorithm.
In few words, Each site with occupied neighbors is assigned the minimum
proper label. at the end we have the following set of np's:
np(1)=0; np(2)=0; np(3)=2; np(4)=0; np(5)=4; np(6)=0;
np(7)=2; np(8)=0; np(9)=np(10)=np(11)=np(12)=np(13)=4; np(14)=8; np(15)=0;
np(16)=0;
Assigning the proper labels to the sites we get the sites labels as
followed.
xy0


xy1


xy2


xy3


4

4


6


4


4



4

4

4




4


16


4



4



4



4

4

15




1


2

2


8






4


14


4

1

1


2

1


2

2

1


2



14



Now, It's simple to check if there is a percolation or not.
If there is the same label at two surfaces (lines in 2D) it means that
there are sites linked between the points there is percolation.
In our example, One can see that there is a percolation between surfaces
(x,y,0) and (x,y,3). the cluster is labeled 4.
The same cluster (#4) is also a percolation cluster between surface
(0,y,z) and (3,y,z). There is no percolation in the ydirection.
TOP
The Project Software
To use this project software, you should have the following
programs on your computer/workspace :
1) C compiler 2) Open GL/Mesa.
NOTE: All the files should be located in same directory.
*** You may read the README.TXT
file and download the codes: perc.c
percolation.h
percolation.c
crystal.c
UNIX users may use main as their compile
file (note: chmod +x main).
Other should do the simple following steps:
1) Compile "perc.c" (The executable file should be named "perc.ex")
: cc perc.c o perc.ex
2) Compile "crystal.c" as an OpenGL file. (The executable file should
be named "crystal.ex") gcc crystal.c o crystal.ex L/usr/local/Mesa1.2.8/lib
lMesaGLU lMesaaux lMesatk lMesaGL lXext lX11 lm L/usr/X11R6/lib
Now, it's cleary you have to run perc.ex and than crystal.ex
TOP
Click here
to view a full revolution of this cluster.
To view several still pictures from different angles click 1
2
3
4
5
TOP
References
Books: Percolation
Theory

Deutscher, G.; Zallen, R.; and Adler, J. (Eds.).
Percolation
Structures and Processes. Bristol: Adam Hilger, 1983.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/rndprc/rndprc.html

Grimmett, G. Percolation.
New York: SpringerVerlag, 1989.

Grimmett, G. Percolation and Disordered Systems. Berlin:
SpringerVerlag, 1997.

Kesten, H. Percolation
Theory for Mathematicians. Boston, MA: Birkhäuser,
1982.

Stauffer, D. and Aharony, A. Introduction
to Percolation Theory, 2nd ed. London: Taylor & Francis, 1992.
Websites:
Links to some interesting sites about percolation:
Prof.
D. Stauffer 2D
percolation  java applet Directed
Percolation Java Applet Books
list
In addition, I thank Mr. Adham Hashibon for his technical help, Mr. Amit
Kanigel for helping me to deal with C, and Mr. David Sa`ada
for his help in OpenGL. All of them are from the Technion.


Copyright © 1999 Technion,
The Israeli Institute of Technology, Physics department, Computational
Physics Group

