Trilateration using unlabeled path or loop lengths

DOI10.1007/S00454-023-00605-XMaRDI QIDQ6191440zbMATH OpenOpenAlexFDO

Authors Ioannis Gkioulekas, Steven J. Gortler, Louis Theran, Todd Zickler

Publication date 9 February 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

distance geometryglobal rigidityrigidity theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Let $mathbfp$ be a configuration of $n$ points in $mathbb{R}^d$ for some $n$ and some $dge2$. Each pair of points defines an edge, which has a Euclidean length in the configuration. A path is an ordered sequence of the points, and a loop is a path that has the same endpoints. A path or loop, as a sequence of edges, also has a Euclidean length, which is simply the sum of its Euclidean edge lengths. We are interested in reconstructing $mathbfp$ given a set of edge, path and loop lengths. In particular, we consider the unlabeled setting where the lengths are given simply as a set of real numbers, and are not labeled with the combinatorial data describing which paths or loops gave rise to these lengths. In this paper, we study the question of when $mathbfp$ will be uniquely determined (up to an unknowable Euclidean transform) from some given set of path or loop lengths through an exhaustive trilateration process. Such a process has been already been used for the simpler problem of unlabeled edge lengths.

Recommendations

• Generic unlabeled global rigidity
• On reconstructing \(n\)-point configurations from the distribution of distances or areas
• Reconstruction of tetrahedra from sets of edge lengths
• WHICH POINT CONFIGURATIONS ARE DETERMINED BY THE DISTRIBUTION OF THEIR PAIRWISE DISTANCES?
• scientific article; zbMATH DE number 4142915

Cites work

• Algorithms in real algebraic geometry
• Analysis of PSLQ, an integer relation finding algorithm
• Elementary structure of real algebraic varieties
• Euclidean distance geometry and applications
• Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
• Generic unlabeled global rigidity
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• Integral distances
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On graphs and rigidity of plane skeletal structures
• On reconstructing \(n\)-point configurations from the distribution of distances or areas
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• Slider-pinning rigidity: a Maxwell-Laman-type theorem
• The algebro-geometric study of range maps
• The non-solvability by radicals of generic 3-connected planar Laman graphs
• The Rigidity of Graphs
• The unassigned distance geometry problem
• WHICH POINT CONFIGURATIONS ARE DETERMINED BY THE DISTRIBUTION OF THEIR PAIRWISE DISTANCES?

This page was built for publication: Trilateration using unlabeled path or loop lengths

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