In this paper we study the problem of computing an exact, or arbitrarily
close to exact, solution of an unrestricted point set stereo matching problem.
Within the context of classical approaches like the Marr-Poggio algorithm,
this means that we study how to solve the unrestricted basic subproblems
created within such approaches, possibly yielding an improved overall
performance of such methods.
We present an $O(n^{2+4k})$ time and $O(n^4)$ space algorithm for exact
unrestricted stereo matching, where $n$ represents the number of points in
each set and $k$ the number of depth levels considered. We generalize the
notion of a $\delta$-approximate solution for point set congruence to the
stereo matching problem and present an $O((\frac{\eps}{\delta})^k n^{2+2k})$
time and $O(\frac{\eps}{\delta} n^2)$ space $\delta$-approximate algorithm
for unrestricted stereo matching ($\eps$ represents measurement inaccuracies
in the image). We introduce new Computational Geometry tools for stereo
matching: the translation square arrangement, approximate translation square
arrangement, and approximate stereo matching tree.