TY - JOUR
T1 - Which point configurations are determined by the distribution of their pairwise distances?
AU - Boutin, Mireille
AU - Kemper, Gregor
PY - 2007/2
Y1 - 2007/2
N2 - In a previous paper we showed that, for any n ≥ m + 2, most sets of n points in ℝm are determined (up to rotations, reflections, translations and relabeling of the points) by the distribution of their pairwise distances. But there are some exceptional point configurations which are not reconstructible from the distribution of distances in the above sense. In this paper, we concentrate on the planar case m = 2 and present a reconstructibility test with running time O(n11). The cases of orientation preserving rigid motions (rotations and translations) and scalings are also discussed.
AB - In a previous paper we showed that, for any n ≥ m + 2, most sets of n points in ℝm are determined (up to rotations, reflections, translations and relabeling of the points) by the distribution of their pairwise distances. But there are some exceptional point configurations which are not reconstructible from the distribution of distances in the above sense. In this paper, we concentrate on the planar case m = 2 and present a reconstructibility test with running time O(n11). The cases of orientation preserving rigid motions (rotations and translations) and scalings are also discussed.
KW - Distribution of invariants
KW - Partial digest problem
KW - Shape recognition
KW - Turnpike problem
UR - http://www.scopus.com/inward/record.url?scp=33847091737&partnerID=8YFLogxK
U2 - 10.1142/S0218195907002239
DO - 10.1142/S0218195907002239
M3 - Article
AN - SCOPUS:33847091737
SN - 0218-1959
VL - 17
SP - 31
EP - 43
JO - International Journal of Computational Geometry and Applications
JF - International Journal of Computational Geometry and Applications
IS - 1
ER -