Page 115 - The Combined Finite-Discrete Element Method

98 CONTACT DETECTION

Sorted array X 3 4 4 4 5 5 5 6

Array Y 7 5 6 7 6 7 8 6

Array D 7 5 3 1 6 4 2 8

Figure 3.26 Second stage of the binary search for cell (5,7).

Sorted array X 3 4 4 4 5 5 5 6

Array Y 7 5 6 7 6 7 8 6

Array D
7 5 3 1 6 4 2 8

Figure 3.27 Third (final) stage of the binary search for cell (5,7).

Once a particular cell and discrete element are identified, a direct check for contact can
be performed.
A search for a particular cell in general requires b steps, where

b = log N (3.43)
2
and N is the total number of discrete elements comprising the system, i.e. the size of
arrays X, Y and D.
In the example given, N was 8, thus the search for cell (5,7) was completed in
three steps:
b = log N = log 8 = 3 (3.44)
2 2
The sorting contact detection algorithm comprises three steps. The first step (mapping
of discrete elements onto the cells) involves a constant number of operations per dis-
crete element. The second step (sorting of integer arrays) involves the total number of
operations per discrete element proportional to
log N (3.45)
2
The third step (searching for particular cells for each discrete element) again involves the
total number of operations per discrete element proportional

log N (3.46)
2