We are given a set of $n$ points on the plane $a_i = \{x^a_i, y^a_i\}$ and $b_i = \{x^b_i, y^b_i\}$.
Assume that the points b are an affine transform of the points a, we can find a matrix $M$ and vector $t$ such that $\sum_{i=0}^{n-1} ||M a_i + t - b_i ||^2$ is minimized, in fact, we can even do so analytically.
Assume however that the points a_i are composed of different subsets to which a different affine transform was applied.
Let $\epsilon$ be a small, tolerance value. A partition $\cup_{j=0}^m P_j = [1\ldots n] \wedge \forall j, k, P_j \cap P_k = \emptyset$ is said to be admissible iff
$$\forall j,~ \exists M_j, t_j,~ \forall i \in P_j,~ ||M_j a_i + t_j - b_i||^2 < \epsilon$$
Simply speaking, we partition the points into different subsets each of which is sent to $b$ with its own affine transform.
An admissible partition always exists because it's always possible to sent a to b exactly if each point is given its own affine transform (in fact, every 3 points can be sent to any other 3 points).
We want to cut up the points in as few pieces as possible: an admissible partition is minimal when it has fewer or equal subsets than any other admissible partitions.
How would one go about finding an admissible partition? Heuristics and approximate solutions are welcome. One approach would be to consider the transformation defined by every triplet of points and try to cluster those together, but this requires looking at $O(n^3)$ transforms.
