Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of transformation of the points in the first set. It's not known which point in the first set corresponds to which point in the second set. What needs to be calculated is if the points of the second set can be seen as the linear transformation of the first set. So basically finding whether there exists a 2 by 2 matrix, which if applied to the first set gives the second set. And if so calculating it.

Should a problem like this be solved using computational geometry, like sweep line algorithm to compare all points between sets?

  • 1
    $\begingroup$ One simple algorithm is to fix two points on one of the sets, go over all pairs of points in the other set, and for each such choice, compute the linear transformation and check whether it fits the rest of the sets. $\endgroup$ Jan 14 at 7:50
  • $\begingroup$ @YuvalFilmus Sorry what do you mean by fixing two points? $\endgroup$ Jan 14 at 19:11
  • 1
    $\begingroup$ Choose, arbitrarily, two points $x,y$ from one set. Then go over all pairs of points $z,w$ from the other set. For each $x,y,z,w$, assuming they are in general position, you can compute the unique linear transformation $T$ such that $Tx=z$ and $Ty=w$, and then check whether it works for all other points. $\endgroup$ Jan 14 at 19:35
  • $\begingroup$ @YuvalFilmus I see, thank you! $\endgroup$ Jan 14 at 22:54
  • 2
    $\begingroup$ Find two adjacent vertices on the boundary polygon of the convex hull of the first set, $p_1$ and $p_2$. Compute the convex hull of the second set. For each linear transformations that map $p_1$ and $p_2$ to two adjacent vertices of the boundary polygon of that convex hull, check if it is a wanted linear transformation. This algorithm runs in about $O(n\log n)$ time on average, $O(n^2\log n)$ time in the worst case, assuming an algorithm with $O(n\log n)$ time is used to compute the convex hull. $\endgroup$
    – John L.
    Jan 15 at 0:51

In 2D, a linear transformation has the form $v \mapsto Mv$ where $M$ is a $2\times 2$ matrix, so the transformation has four parameters. Thus, the transformation is uniquely determined if you have two points $p_1,p_2$ from the first set and two points $q_1,q_2$ and if you know that $p_1$ transforms to $q_1$ and $p_2$ to $q_2$. You can find this linear transformation explicitly by solving a system of linear equations.

Consequently, the following algorithms works:

  1. Pick two points $p_1,p_2$ arbitrarily from the first set.
  2. For each possible way to pick two points $q_1,q_2$ from the second set:
    • Find the unique linear transformation $T$ that maps $p_1$ to $q_1$ and $p_2$ to $q_2$.
    • Check whether applying $T$ to the first set gives you exactly the second set. If so, output $T$ and halt.
  3. If you reach this point, output that no such linear transformation exists and halt.

This algorithm is guaranteed to be correct: it will find the linear transformation, if any exists, because we have tried all possible pair of points that $p_1,p_2$ could match with.

The worst-case running time is $O(n^3)$, if $n$ is the number of points in each set. That's because you loop over ${n \choose 2} = O(n^2)$ pairs of points in step 2. Each iteration of the loop involves solving a system of four linear equations (takes $O(1)$ time) and checking whether it is a valid solution (could take $O(n)$ time in the worst case, since you might have to apply $T$ to each point in the first set).

However, heuristically, I expect the running time will typically be $O(n^2)$. That's because typically you can reject most candidate transformations $T$ immediately: if you apply $T$ to one point in the first set, and get a result that is not in the second set, you can reject $T$ without applying it to any other points in the first set. Thus, heuristically, I expect that typically each iteration of the loop will usually complete in $O(1)$ time. That said, there do exist arrangements of the points where this is not correct.

The generalization of this algorithm is RANSAC, which can handle the situation where most points of the first set can be matched to the second set but some cannot.

  • $\begingroup$ Thank you! Does the same algorithm apply for 3D? $\endgroup$ Jan 14 at 22:58
  • 1
    $\begingroup$ @LennyWhite, yes. You'll need 3 points rather than 2. $\endgroup$
    – D.W.
    Jan 15 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.