A fast optimal algorithm for L₂ triangulation

This paper presents a practical method for obtaining the global minimum to the least-squares (L₂) triangulation problem. Although optimal algorithms for the triangulation problem under L_∞-norm have been given, finding an optimal solution to the L₂ triangulation problem is difficult. This is because the cost function under L₂-norm is not convex. Since there are no ideal techniques for initialization, traditional iterative methods that are sensitive to initialization may be trapped in local minima. A branch-and-bound algorithm was introduced in [1] for finding the optimal solution and it theoretically guarantees the global optimality within a chosen tolerance. However, this algorithm is complicated and too slow for large-scale use. In this paper, we propose a simpler branch-and-bound algorithm to approach the global estimate. Linear programming algorithms plus iterative techniques are all we need in implementing our method. Experiments on a large data set of 277,887 points show that it only takes on average 0.02s for each triangulation problem.