Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 05:50, 11 September 2016

Revision as of 10:47, 11 September 2016

Line 1:

{{multiple issues|

== Introduction ==

{{Capitalization|date=September 2016}}

<div style="text-align:justify">

{{Inappropriate person|date=September 2016}}

{{Dead end|date=September 2016}}

{{Orphan|date=September 2016}}

{{Primary sources|date=September 2016}}

}}

The Hoshen-Kopelman Algorithm is simple and efficient algorithm for labelling clusters on a grid, where grid is a regular network of cells, where each cell may be “occupied” or “unoccupied”. This algorithm is based on well-known union-finding algorithm. The algorithm was originally described in [http://journals.aps.org/prb/abstract/10.1103/PhysRevB.14.3438 Percolation and Cluster Distribution. I. Cluster Multiple Labeling Technique and Critical Concentration Algorithm] by J. Hoshen and R. Kopelman.

</div>

== Percolation Theory ==

<div style="text-align:justify">

Percolation theory is the study of the behavior and statistics of clusters on lattices. Suppose we have a large square lattice where each cell can be occupied with the probability p and empty with probability 1 – p. Each group of neighboring occupied cells forms a cluster. Neighbors are defined as cells having a common side but not those sharing only a corner i.e. we consider 4x4 neighborhood. (top, bottom, left, right). Each occupied cell is occupied independently of the status of its neighborhood. The number of clusters, size of each cluster and their distribution are important topics in percolation theory.

</div>

== Union-Find Algorithm ==

Line 55 ⟶ 57:

return y;

}

== Example ==

{{empty section|date=September 2016}}

== Applications ==

{{empty section|date=September 2016}}

== More Clustering Algorithms ==

Line 69 ⟶ 71:

# Gaussian(EM) clustering algorithm

# Quality threshold clustering algorithm

==References==

[1] - http://journals.aps.org/prb/abstract/10.1103/PhysRevB.14.3438

{{Uncategorized|date=September 2016}}