Mesh generation by parallel processing - Finite Element Mesh Generation - page 390

7.3 PARALLEL DELAUNAY TRIANGULATION IN 2D

Following the idea of the zonal point insertion, points are first partitioned into cells by
means of a regular grid, which are then grouped into zones according to the number of
processors available. Points are inserted cell by cell within a zone simultaneously with one
processor operating in each zone.

7.3.1 Points partitioned into cells
Let N be the number of points in a 2D Delaunay triangulation, and n be the average number
of point desirable in a cell. Then

nN x N y = N (7.1)

where
N x = number of cell divisions along the x-axis
N y = number of cell divisions along the y-axis

and the number of cells, N c = N x N y .
Let x min , y min , x max , y max be the bounds of the (x,y) co-ordinates of the point set. Compute
the range in x, R x = x max - x min , and the range in y, R y = y max - y min . N x and N y can be deter-
mined by substituting λR x = N x and λR y = N y into Equation 7.1.
The most important requirement in a spatial partition of points into cells is to ensure that
each point belongs to one and only one cell, and the sum of points in all the cells equal to
the total number of points, i.e.

N

c

∑ 1

Nn = wheren = numberof pointsin celli

if if

if =

7.3.2 Grouping cells into zones
Let N p = Z x Z y be the number of processors available for parallel insertion, where Z x and Z y
are the zonal divisions along the x- and y-axes, respectively, as shown in Figure 7.3. Cells are
grouped into zones such that the number of cells in each zone is given by

N
Z

N
Z

y

x

NNINT = NINT whereNINT (.)returnsthe nearestinteger

z

x y

For the best performance of parallel insertion, the number of zones ought to be an integral
multiple of the number of processors available; for instance, division into 12 zones for three
or four processors is a sound division. However, division into 12 zones for eight processors
may not be that appropriate, because 12 = 8 + 4, and not all processors will be working to
their full capacity all the time. However, since we are working with millions of points, the
partition into cells and the division into zones, which are multiples of the number of proces-
sors, will never be a problem. The number of cells in some zones near the boundary may
not be the same if N x /Z x or N y /Z y is not a whole number. Such a variation would not cause