Recovery of the metric structure of a pattern of points using minimal information

A new method is proposed in order to reconstruct the geometrical configurat ion of a large points set using minimal information, The paper develops alg orithms based on graph and kinematics theories to determine the minimum num ber of distances, needed to uniquely represent n points in d-dimensional Eu clidean space. Therefore, it is found that this theoretical minimum is d(n - 2) + 1 interpoint distances. The method is evaluated, on the basis of bas ic parameters, by means of Monte Carlo simulation using genetic algorithms for better optimization procedures, This evaluation takes into account the real case where the metric informations are interpoint dissimilarities inst ead of exact Euclidean distances, Two applications on real data successfull y illustrate the efficiency of the method. Finally, on the basis of Monte C arlo results, the authors provide some practical recommendations to experim enters who wish to use the method in order to scale a many-objects set.