Point Sets Up to Rigid Transformations areDetermined by the Distribution of their PairwiseDistancesDaniel ChenDecember 6, 2008AbstractThis report is a summary of [BK06], which gives a simpler, albeit lessgeneral proof for the result of [BK04].1 Introduction[BK04] and [BK06] study the circumstances when sets of n-points in Euclideanspace are determined up to rigid transformations by the distribution of unlabeledpairwise distances. In fact, they show the rather surprising result that any setof n-points in general position are determined up to rigid transformations bythe distribution of unlabeled distances.1.1 Practical MotivationThe results of [BK04] and [BK06] are partly motivated by experimental resultsin [OFCD]. [OFCD] is an experimental study evaluating the use of shape distri-butions to classify 3D objects represented by point clouds. A shape distributionis a the distribution of a function on a randomly selected set of points fromthe point cloud. [OFCD] tested various such functions, including the angle be-tween three random points on the surface, the distance between the centroidand a random point, the distance between two random points, the square rootof the area of the triangle between three random points, and the cube root ofthe volume of the tetrahedron between four random points. Then, the distri-butions are compared using dissimilarity measures, including χ2, Battacharyya,and Minkowski LNnorms for both the pdf and cdf for N = 1, 2, ∞.The experimental results showed that the shape distribution function thatworked best for classification was the distance between two random points andthe best dissimilarity measure was the pdf L1norm. [BK04] provides a partialtheoretical justification for these results by showing that there exists a generalposition assumption such that the distribution of pairwise distances completelydetermines the shape of the point set. This result, however, only considers the1case when the distribution of pairwise distances are exactly the same. Whethera similar result holds when the distributions are close is an open problem.2 PreliminariesDefinition 2.1 (General Position). We use the definition of general positiongiven in [M]. Let a set of n points in Rdbe specified by a vector t = (t1, t2, . . . , tm)for m = dn. Then, a general position condition is a condition that can beexpressed asVipi(t) 6= 0 for a countable number of polynomials pi.The intuition behind a general position condition is that configurations ingeneral position lie arbitrarily close to any given configuration, as polynomialsonly have a finite number of zeros. [BK04] and [BK06] show a general positioncondition that also results in the point configuration being completely deter-mined by the distribution of pairwise distances up to rigid transformations. Wedefine rigid transformations as the following:Definition 2.2 (Rigid Transformation). Let p be a point in Rm. Then a rigidtransformation is a function R : Rm→ Rmthat can be written as R(p) = Mp+Twhere M is an orthogonal m-by-m matrix and T is a column vector in Rm.Definition 2.3 (Distribution of Pairwise Distances). Given a set of points P ,let the distribution of pairwise distances d(P ) be the multiset {||pi− pj||}i<j.We also define reconstructibility from pairwise distances as the following:Definition 2.4 (Reconstructibility from Pairwise Distances). We say that p1, . . . , pn∈Rmis reconstructible from pairwise distances if for every q1, . . . , qn∈ Rmwiththe same distribution of pairwise distances, there exists a rigid transformation Rand a permutation π of {1, . . . , n}, such that P (pi) = qπ(i)for every i ∈ 1, . . . , n.3 Folklore LemmaBecause it is tricky to work directly with point sets under rigid transformations,we will instead compare instead the distance matrices. The Folklore Lemmastates that two configurations of points have the same distance matrices if andonly if there exists a rigid transformation that maps one configuration to theother. The following is an adaptation of the proof given in [BK04], howeverusing the language of more elementary linear algebra.Lemma 3.1 (Folklore Lemma). Let p1, . . . , pnand q1, . . . , qnbe points in Rm.If ||pi− pj|| = ||qi− qj|| for every i, j in 1, . . . , n, then there exists a rigidtransformation R such that R(pi) = qifor all i.2Proof. Let xi= pi− pnand yi= qi− qnfor i = 1, . . . , n. We claim thathxi, xji = hyi, yji for all i, j. To see this, we have the following calculation:hxi, xji = hpi− pn, pj− pni=hpi− pn, pi− pni + hpj− pn, pj− pni − hpi− pj, pi− pji2=||pi− pn|| + ||pj− pn|| − ||pi− pj||2=||qi− qn|| + ||qj− qn|| − ||qi− qj||2=hqi− qn, qi− qni + hqj− qn, qj− qni − hqi− qj, qi− qji2= hqi− qn, qj− qni = hyi, yjiNow, let X = [x1, · · · , xn] and Y = [y1, · · · , yn]. We have shown abovethat XTX = YTY . Now, XTX is symmetric and positive semidefinite, andhence can be written as QΛQTfor an orthogonal Q and a non-negative diagonalmatrix Λ. Since Λ, is non-negative, we can write XTX = YTY = QΛ1/2Λ1/2QT.Therefore, using the singular value decomposition, we can write X as UXΛ1/2QTand Y as UYΛ1/2QTfor orthogonal UXand UY. Then, we can write Y = M Xfor orthogonal M = UYUTX. Moreover, it is easy to verify that M xi= yifor i = 1, . . . , n. To finish the proof, we note that M (pi− pn) = qi− qnorqi= M pi+ qn− Mpnso there is a rigid transformation from pito qiwith theorthogonal matrix M and translation vector qn− Mpn.Now, it is obvious that the distribution of pairwise distances remains thesame after any rigid transformation. We note that it is not the case that allpoint configurations are reconstructible from pairwise distances: [B] came upwith a counterexample for a set of points in one dimension as follows:P = {0, 1, 4, 10, 12, 17} Q = {0, 1, 8, 11, 13, 17}It can be verified that the distribution of distances is the multiset:d(P ) = d(Q) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17}for both point sets while it is also clear that there is no isometry from P toQ. [BK04] show a counterexample in two dimensions, see Figure 1. [BK04]and [BK06], however, show the surprising result that there is a general positioncondition for n points where n ≥ m + 2 that implies the points are in factreconstructible from pairwise distances. For concreteness, we will describe theproof for n-point configurations for n ≥ 5 in R2.4 Most Point Configurations are ReconstructibleWith the Folklore Lemma in