Reconstruction in one dimension from unlabeled Euclidean lengths

Robert Connelly, Steven J. Gortler, Louis Simon Theran*

*Corresponding author for this work

Research output: Contribution to journal β€Ί Article β€Ί peer-review

Abstract

Let G be a 3-connected ordered graph with n vertices and m edges. Let be a randomly chosen mapping of these n vertices to the integer range {1, 2, 3, ... 2b} for b β‰₯ m2. Let be the vector of m Euclidean lengths of G’s edges under p. In this paper, we show that, with high probability over p, we can efficiently reconstruct both G and p from 𝓁. This reconstruction problem is NP-HARD in the worst case, even if both G and 𝓁 are given. We also show that our results stand in the presence of small amounts of error in 𝓁, and in the real setting, with sufficiently accurate length measurements. Our method combines lattice reduction, which has previously been used to solve random subset sum problems, with an algorithm of Seymour that can efficiently reconstruct an ordered graph given an independence oracle for its matroid.
Original languageEnglish
Number of pages27
JournalCombinatorica
VolumeFirst online
Early online date11 Jul 2024
DOIs
Publication statusE-pub ahead of print - 11 Jul 2024

Keywords

  • Rigidity theory
  • Distance geometry
  • Graph realization problem

Fingerprint

Dive into the research topics of 'Reconstruction in one dimension from unlabeled Euclidean lengths'. Together they form a unique fingerprint.

Cite this