WHICH POINT CONFIGURATIONS ARE DETERMINED BY THE DISTRIBUTION OF THEIR PAIRWISE DISTANCES?

DOI10.1142/S0218195907002239zbMATH Open1114.65014arXivmath/0311004MaRDI QIDQ3430331FDOQ3430331

Mireille Boutin, Gregor Kemper

Publication date: 21 March 2007

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Abstract: In a previous paper we showed that, for any $ngem+2$, most sets of $n$ points in $R{R}^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 present a reconstructibility test with running time $O(n^{11})$. The cases of orientation preserving rigid motions (rotations and translations) and scalings are also discussed.

Full work available at URL: https://arxiv.org/abs/math/0311004

zbMATH Keywords

shape recognitionpartial digest problemturnpike problemdistribution of invariants

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• The Magma algebra system. I: The user language
• Title not available (Why is that?)
• Generalized Procrustes analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• On reconstructing \(n\)-point configurations from the distribution of distances or areas
• A counterexample to a theorem of S. Piccard
• Invariants of \(S_ 4\) and the shape of sets of vectors

Cited In (10)

• Constructing uniquely realizable graphs
• Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures
• The unassigned distance geometry problem
• Reconstructing finite sets of points in \(R^n\) up to groups of isometries
• On reconstructing \(n\)-point configurations from the distribution of distances or areas
• Trilateration using unlabeled path or loop lengths
• Distances and isomorphism between networks: stability and convergence of network invariants
• The beltway problem over orthogonal groups
• Generalized shapes and point sets correspondence and registration
• Assigned and unassigned distance geometry: applications to biological molecules and nanostructures

Uses Software

• Magma

   Recommendations

• Title not available (Why is that?) 👍 👎
• Point sets with distinct distances 👍 👎
• On reconstructing \(n\)-point configurations from the distribution of distances or areas 👍 👎
• On the distinct distances determined by a planar point set 👍 👎
• PARTITION-EQUIVALENT n-POINTS CONFIGURATIONS WITH TWO DISTANCES 👍 👎
• Title not available (Why is that?) 👍 👎
• Distance distribution between two random points in arbitrary polygons 👍 👎
• Bounds on Point Configurations Determined by Distances and Dot Products 👍 👎
• Distance sets of well-distributed planar point sets 👍 👎
• Distribution of Points in n-Space 👍 👎

This page was built for publication: WHICH POINT CONFIGURATIONS ARE DETERMINED BY THE DISTRIBUTION OF THEIR PAIRWISE DISTANCES?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3430331)