On the Performance of Triangulation-Based Multiple Shooting Method for 2D Geometric Shortest Path Problems - Transactions on Large-Scale Data-and Knowledge-Centered Systems - page 53

Table 1. The run time (in seconds) of Algorithm 1 and the run times (in seconds) of
triangulation and dual tree construction for the funnel algorithm

No. of cutting segments Algorithm 1 Triangulation Dual tree construction
0

41,828.75 21,129.27 16,325.46

5 7,344.34 4,464.89 2,723.89

10 4,060.89 2,493.57 1,467.05

50 858.65 497.55 192.49

100 504.99 251.51 96.27

500 284.62 51.08 19.05

1000 275.76 26.21 9.74

Fig. 5. The run time of Algorithm 1, triangulation, and dual tree constructing

However, the time of the refinement is also large comparing with the time
of the triangulation and the dual tree construction as the number of cutting
segments is increased. This means that the collinear condition of Algorithm 1
might be di cult to reach as a large number of cutting segments (see Fig. 5 ).

3.2 Memory Usage

Another task for the funnel algorithm is the dual tree construction. If each
triangle of the triangulation is considered as a node of the tree, then the tree
should be a binary one. An arbitrary triangle can be chosen to become the root
of the tree. We start at the root and then construct the tree by adding new nodes
based on the adjacent relationship between triangles. For each step of adding
a new node, however, we need to traverse the current tree starting at the root.
Therefore, a memory space of a node type must be allocated. This is why in case