Point Set Transformations using Given Groups

We study transforming one point set A to an equal-size point set B optimally, where translating any of a predefined set of groups of points incurs a cost independent of its size. We consider two objectives: minimizing the number of groups moved (Cardinality) and minimizing the total translation length of the groups (Length). When a matching between A and B is given – that is, we know which point moves to which other point – we prove that minimizing Cardinality is NP-hard in general, but efficiently solvable when the given groups form a hierarchy. Without a prescribed matching, we prove that both minimizing Cardinality and Length is NP-hard.