Which point configurations are determined by the distribution of their pairwise distances?

Mireille Boutin, Gregor Kemper

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)31-43
Number of pages13
JournalInternational Journal of Computational Geometry and Applications
Volume17
Issue number1
DOIs
StatePublished - Feb 2007

Keywords

  • Distribution of invariants
  • Partial digest problem
  • Shape recognition
  • Turnpike problem

Fingerprint

Dive into the research topics of 'Which point configurations are determined by the distribution of their pairwise distances?'. Together they form a unique fingerprint.

Cite this