Next: 5.2 Particle Movement Up: 5 Algorithmic Issues Previous: 5 Algorithmic Issues Contents
This works well for problems with relatively low coverage levels. Unfortunately, hydrogen tends to have a fairly high coverage level on our silicon surfaces (between 0.1 to .5 ML). Thus the classic particle placement algorithm, though made cheaper by spatial binning, still yields too many rejections to work well for our problems.
Thus we have implemented an alternate particle placement algorithm.
We start by creating a bin for each particle column in a given
dimension (we choose the 
dimension). We then generate the
-coordinates of the particles by randomly choosing a bin, and
placing a particle in it. Only if a bin gets filled (i.e. there are as
many particles as 
-coordinates) do we reject particle placements.
This work is linear in the number of particles, and tends to have a
very high efficiency level.
Next, we place the possible -coordinates in an array. By use of a
linear-time, random shuffle algorithm, we then choose the
-coordinates for the particles in each bin. Since we are choosing
from a shuffled ``deck'' of all potential -coordinates, we cannot
possibly have position conflicts in this step. By virtue of the way a
random shuffle works, we only need to do as much work per bin as the
number of particles, and do not need to reset the ``deck'' between
bins. Thus our overall algorithm is linear for particle placement.
Chris Siefert and Molly Moore 2002