Near Extensions and Alignment of Data in R(superscript)n

21 The Unlabeled Correspondence Configuration Problem and Optimal Transport

The work below is motivated by the difficulty in trying to match point sets in the absence of labels in the sense that often one does not know which point to map to which. This is referred to commonly as the unlabeled problem. We discuss briefly optimal transport.

21.1 Unlabeled Correspondence Configuration Problem

In the paper [26], we investigate ways to align two point configurations by first finding a correspondence between points and then constructing a function which aligns the configurations. The terms reordering and relabeling are used interchangeably. Examples are given in [26] to show, for example, in , when in certain configurations, some distributions of distances do not allow good alignment and how we can partition certain configurations into polygons in order to construct maximum possible correspondences between these configurations, considering their areas. Algorithms are described for certain configurations with matching points along with examples where we find a permutation which gives us a relabeling, and also the required affine transformation which aligns certain configurations. See also Figures 21.1–21.2.

Figure 21.1 Two different 4-point configurations with the same distribution of ...