Triangulation of a three-dimensional point from n >=2 two-dimensional images can
be formulated as a quadratically constrained quadratic program. We propose an
algorithm to extract candidate solutions to this problem from its semidefinite
programming relaxations. We then describe a sucient condition and a polynomial time
test for certifying when such a solution is optimal. This test has no false
positives. Experiments indicate that false negatives are rare, and the algorithm
has excellent performance in practice. We explain this phenomenon in terms of the
geometry of the triangulation problem.