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

DOI10.1142/S0218195907002239MaRDI QIDQ3430331zbMATH OpenFDO

Authors Mireille Boutin, Gregor Kemper

Publication date 21 March 2007

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

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)

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.

Recommendations

• scientific article; zbMATH DE number 865979
• 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
• scientific article; zbMATH DE number 4019892
• 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

Cites work

• scientific article; zbMATH DE number 1229396 (Why is no real title available?)
• scientific article; zbMATH DE number 578417 (Why is no real title available?)
• scientific article; zbMATH DE number 3080144 (Why is no real title available?)
• A counterexample to a theorem of S. Piccard
• Generalized Procrustes analysis
• Invariants of \(S_ 4\) and the shape of sets of vectors
• On reconstructing \(n\)-point configurations from the distribution of distances or areas
• The Magma algebra system. I: The user language

Cited in

(12)

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

Describes a project that uses

Uses Software

• Magma

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)