Which Point Configurations are Determined by theDistribution of their Pairwise Distances?Mireille Boutin and Gregor KemperMarch 14, 2006AbstractIn a previous paper we showed that, for any n ≥ m + 2, most sets of n points in Rmare determined(up to rotations, reflections, translations and relabeling of the points) by the distribution of their pairwisedistances. But there are some exceptional point configurations which are not reconstructible from thedistribution of distances in the above sense. In this paper, we concentrate on the planar case m = 2and present a reconstructibility test with running time O(n11). The cases of orientation preserving rigidmotions (rotations and translations) and scalings are also discussed.IntroductionIn this paper, we present a quick and easy (but slightly imperfect) solution to the problem of characterizingthe shape of sets of n points in Euclidean space, so-called n-point configurations, for any positive integer n.More precisely, an n-point configuration is a collection of n points in Rm. Point configurations often arise inbiological and medical imagery, as well as in the fields of archaeology, astronomy and cartography, to namejust a few. For example, stellar constellations, minutiae of fingerprints, and distinguished points (landmarks)on medical images represent point configurations.An important problem of computer vision is that of recognizing point configurations. In other words,the problem is to determine whether two point configurations have the same shape, that is to say, whetherthere exists a rotation and a translation (sometimes a reflection and/or a scaling are allowed as well) whichmaps the first point configuration onto the second. Let us first concentrate on the case of rigid motions,i.e. rotations, translations and reflections in Rm. Note that any rigid motion can be written as (M, T ), whereM is an orthogonal m-by-m matrix and T is an m-dimensional (column) vector.One of the biggest difficulties in trying to identify point configurations up to rigid motions is the absenceof labels for the points: one does not know, a priori, which point is going to be mapped to which. If the pointswere already labeled in correspondence, then, following the so-called Procrustes approach (Gower [10]), onecould analytically determine a rigid motion which maps the first string as close as possible (in the L2sense,for example) to the second. The statistical analysis of such methods is presented in Goodall [9]. Anotherway to proceed would be to compare the pairwise (labeled) distances between the points of each pointconfigurations (Blumenthal [3]). Indeed, the following well known fact holds. See, for example, Boutin andKemper [5] for a simple proof.Proposition 0.1. Let p1, . . . , pnand q1, . . . , qnbe points in Rm. If kpi− pjk = kqi− qjk for every i, j =1, . . . , n, then there exists a rigid motion (M, T ) such that M pi+ T = qi, for every i = 1, . . . , n.A variety of methods have been developed for labeling the points of two n-point configuration in corre-spondence. See, for example, Hartley and Zisserman [12] for a description of some of these methods. Butlabeling the points is a complex task which we would much rather do without. A natural tool for dealingwith this problem is invariant theory (Hilbert 1993, Olver 1999, Derksen & Kemper 2002), which is thestudy of algebraic forms that remain unchanged under certain transformations such as the ones defined by12Mireille Boutin and Gregor KemperValue # of Occurrences1 4√2 2Table 1: Distribution of distances of a unit square.group actions. For example, the sum of two points p1, p2in R2is invariant under a permutation of the la-belings of the two points (p1, p2) → (p2, p1). Invariant theory suggests a possible approach for recognizingunlabeled points. The idea is to compare certain functions of the pairwise distances between the points of theconfiguration which have the property that they are unchanged by a relabeling of the points. These are oftencalled graph invariants and have been computed in the case of n = 4 by Aslaksen et al. [1], and n = 5 bythe second author [7, page 220]. Unfortunately, the case n = 6 or larger still stands as a computational chal-lenge. Moreover, the invariants used are polynomial functions of the distances whose number and degreesincrease dramatically with n. They are thus very sensitive to round off errors and noise.In the following, we study an alternative approach based on the use of a very simple object: the distri-bution of the pairwise distances. The distribution of the pairwise distances of an n-point configuration is anarray which lists all the different values of the pairwise distances between the points in increasing order andthe number of times each value occurs. For example, the distribution of distances of four points situated atthe corners of a unit square is given in Table 1.Obviously, such a distribution remains unchanged under any rigid motion of the point configuration aswell as any relabeling of the points. For n = 1, 2 or 3, it is easy to see that the distribution of distancescompletely characterizes the n-point configuration up to a rigid motion. The case m = 1 was studied byPiccard ((Piccard 1939)). She claimed that two n-point configurations in R whose pairwise distances areall distinct are the same up to a rigid motion if and only if their distributions of distances are the same.Unfortunately, this claim was disproved by Bloom who provided a counterexample with n = 6 (Bloom1977). For any n ≥ m + 2, we proved that, most of the time, this distribution of the pairwise distancescompletely characterizes the shape of the point configuration (see [5, Theorem 2.6]).To simplify our discussion, we introduce the concept of reconstructibility from distances.Definition 0.2. We say that the n-point configuration represented by p1, . . . , pn∈ Rmis reconstructiblefrom distances if, for every q1, . . . , qn∈ Rmhaving the same distribution of distances, there exists a rigidmotion (M, T ) and a permutation π of the labels {1, . . . , n} such that M pi+ T = qπ(i), for every i =1, . . . , n.In the following, we shall often identify a point configuration and one of its representation p1, . . . , pn∈Rm. This is done for simplicity and we hope it will not create any confusion.The actual reconstruction of a point configuration will not be addressed in this paper. However, to putthis research in context, we would like to make a few remarks. The problem of