Computational complexity.

In order to evaluate the computational cost of the above algorithms, we apply them to the image of figure . For this test image, we compute the B_d-geodesic DT for balls of size $1 \leq d \leq 9$ using the three same algorithms as in section .
Figure shows the computational cost of the bucket sorting and circular propagation algorithms according to the ball size d. The costs of the circular propagation algorithms are independent of the ball size d. In contrast, the bucket sorting algorithm has a cost highly dependent from the ball size. It is sometimes as fast as the others, and sometimes more than 4 times slower.
Similar results were obtained from a variety of other test images.

  

Figure 8.5: Computational complexity of the geodesic DT algorithms