next up previous contents
Next: Summary of Performance and Up: Selecting a Tracking Algorithm Previous: Events Handling and Algorithmical

   
Computational Efficiency and Convergence

The processing times of the algorithms are discussed in section 5.4. The iterative algorithms SJ87 and SS90 are not suitable for working with many trajectories because of the high computational cost that becomes prohibitive very soon as $N$ grows. These algorithms cannot efficiently constrain the correspondences, which leads to combinatorial explosion. (The unconstrained motion correspondence is an NP-complete problem.) A critical value of $N$ is around 40, when SJ87 becomes practically impossible to systematically test. As pointed out in [9], this greedy exchange algorithm may sometimes not converge at all, going into an infinite loop -- if the iterations are not forced to stop by limiting their number, as we actually do. Apparently, this occurs more frequently as the point density increases. In the original paper [11], no efficient stopping rule was formulated for such cases.



Dmitry Chetverikov
1998-11-24