|
|
|
|
|
|
|
|
Which point configurations are reconstructible from the distribution of their pairwise distances?
This research was inspired by the problem of object recognition in computer vision. We consider the question: "Is any point configuration uniquely determined, up to a rigid motion, by the set of its pairwise (unlabeled) distances?". As we will show by counterexamples, the answer is no. However, counterexamples $p_1,\ldots ,p_n \in {\mathbb R}^m$ are extremely rare, as they must satisfy a polynomial equation $f(p_1,\ldots, p_n)=0$. In general, the polynomial $f$ is too big to be stored in a computer but we give an algorithm in $O(n^{m^2+3m+1})$ steps to check whether $p_1,\ldots,p_n\in {\mathbb R}^m$ satisfies this polynomial equation.
The distribution of the pairwise distances of a point configuration can thus be used to characterize the shape of this point configuration. In particular, one does not need to label the points of two configurations in correspondence in order to compare their shape. Similarly, we have shown that the distribution of triangular areas and generalized cross-ratios can be used to characterize point configurations up to an equi-affine and a projective transformation respectively.
This is joint work with Gregor Kemper (TU Munich).
Tuesday, January 13, 2004, 245 Altgeld Hall, 4:00 p.m.
Mathematics Colloquia homepage