patternMinor
For two sets of points find if second one is result of linear transformation of the first
Viewed 0 times
resultlinearthepointstwoonetransformationforsecondfind
Problem
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?
Should a problem like this be solved using computational geometry, like sweep line algorithm to compare all points between sets?
Solution
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:
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.
Consequently, the following algorithms works:
- Pick two points $p_1,p_2$ arbitrarily from the first set.
- 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.
- 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.
Context
StackExchange Computer Science Q#134333, answer score: 3
Revisions (0)
No revisions yet.