__Sets of Points__

Consider 2 photos P and Q. These can be viewed as sets of points P= {p

_{1}, p_{2},..., p_{N}} and Q={q_{1}, q_{2},..., q_{N}} where the p_{i }'s and q_{i}'s are points ( x , y ) in the plane. We first merge Q with P so that no point of Q lies on a point of P.

The crucial observation is the following:

Suppose there exists a position of P and Q such that we can find a one-to-one mapping f from P to Q, for which the lines defined by the pairs of points ( p_{i}, f(p_{i})) are parallel (see figure 1).

Then it is possible to construct a set of points R={ r_{i}}, i=1,...,N such that P and Q are orthogonal projections of R.This can be done as follows:

1. Rotate the plane P so that P and Q are orthogonal.

2. Draw the lines L_{p1},L_{p2},...,L_{pN}orthogonal to P passing through p_{1},p_{2},...,p_{N}.

3. Similarly, draw the lines L_{f(p1)}, L_{f(p2)},..., L_{f(pN)}orthogonal to Q passing through f (p_{1}), f (p_{2}) ,..., f (p_{N}).

4. For all i=1,..,N, the line L_{pi}intersects L_{f(pi)}at a point r_{i}.It's clear that the set R={ r

_{i}}_{i=1,..,N}satisfies our conditions (see figure 2).The problem of constructing R can therefore be reduced to the one of finding the appropriate position for P and Q together with the bijection f.

We will first discuss the labelled case, that is the case where the bijection f is known.

Labelled case:

Given pairs of points (pLet's now consider the unlabelled case._{i}, q_{i}=f(p_{i})), where i=1,...,N, we'd like to find a position of P for which the lines p_{1}q_{1}, p_{2}q_{2},..., p_{n}q_{n}are parallel. We proceed in the following manner:

Let's fix a point p* belonging to P, say p_{1}. For all points p_{j}in P, we rotate p_{j}about p* by an angle t. Consider the lines p_{j}q_{j}( j=1,...,N ). Their slopes will vary as the angle of rotation about p* changes.

Denote by s_{j}( t ) the slope functions of the lines joining p_{j}and q_{j}( j=1,...,N ). We want to find a value of t for which the lines p_{j}q_{j}( j=1,...,N ) are parallel. This is true if and only if s_{j}( t ) = s for all j=1,...,N for some value of t and some constant s. How do we find t? We just pick a slope function, say s_{1}( t ), and compute its intersections with the remaining n-1 slope functions. If a value t* of t that satisfies the above condition exists, then all n-1 functions must cross s_{1}( t ) at a common point.

It can be shown that the functions s_{j}( t ) can be broken down into four alternately increasing and decreasing pieces. This implies that the maximum number of crossings between two such functions is 4 (constant). Therefore, checking for all possible intersections between s_{1}( t ) and the remaining n-1 functions takes linear time and space.

Unlabelled case:

The idea is essentially the same as for the labelled case, except that we now need to consider all possible combinations of points p and q, where p is in P and q is in Q. There are O( n^{2}) such combinations. Hence, we now have O( n^{2}) slope functions s_{i j }( t ) corresponding to the O( n^{2}) lines.

As before, we pick a slope function s_{1 1}( t ) and compute for each of its four monotone (ie either increasing or decreasing) pieces its intersections with the remaining O( n^{2}) functions. For each piece, we sort the resulting intersections in O ( n^{2}log n^{2}) = O ( n^{2}log n ) to determine if n of them are repeated.

This whole procedure can therefore be accomplished in O ( n^{2}log n ) time and O ( n^{2}) space.