Information Technology Reference
In-Depth Information
of huge data, the memory space required in the funnel algorithm is large. Again,
the method given in [ 1 ] helps us to overcome this issue, because the triangulation
is only required on sub-polygons.
In our implementation, tree traversal type is the in-order searching without
recursion. Table 2 shows the peak memory usages in two cases. In the first case, if
we free the memory cells of nodes after each searching, then the required memory
is small. The second one requires more memory space, since the memory is only
cleaned up after whole dual tree is constructed.
Table 2. The peak memory (MB) of Algorithm 1 in which the shortest paths in sub-
polygons are computed by using the funnel algorithm
No. of cutting segments Free on nodes Free on trees
0
3.218
579,544.000
5
0.538
16,148.701
10
0.296
4,880.905
50
0.065
234.408
100
0.033
61.639
100
0.007
2.922
1000
0.004
0.827
Fig. 6 shows that if we implement Algorithm 1 using the funnel one for sub-
polygons in which the memory is cleaned up at each node of the dual tree, then
Algorithm 1 is ecient. This is obtained because of small required memory space
of dual tree processing.
Fig. 6. The required memory is too large as number of cutting segments is reduced
 
Search WWH ::




Custom Search