Euclidean distance geometry and applications

Leo Liberti; Carlile Lavor; Nelson Maculan; Antonio Mucherino

Source-linked AI summary

Euclidean distance geometry and applications

Leo Liberti, Carlile Lavor, Nelson Maculan, Antonio Mucherino

arXiv:1205.0349v1May 2, 2012q-bio.QM

TL;DR

Euclidean distance geometry asks how to realize points from incomplete distance data, a problem underlying molecular conformation, sensor-network localization, and statics. This survey synthesizes its theory and applications, highlighting algorithms and tractable subclasses while concluding that the mature field offers informative results but cannot be covered completely.

Problem
The Distance Geometry Problem asks whether weighted graph distances can be realized by points in a specified Euclidean space.
Method
The paper surveys Euclidean distance geometry theory, algorithms, and applications in molecular conformation, sensor localization, and statics.
Results
The survey presents an informative account of major theoretical results and applications, including methods that realize graphs with thousands of vertices and edges in under five seconds.
Takeaways & Limitations
Euclidean distance geometry provides a mature foundation for biological, statistical, and engineering applications involving partial distance information.
Takeaways & Limitations
Hydrogen-only discretization works on artificial instances but has limitations on real NMR data, requiring re-orders.

Abstract

from arXiv · show

Euclidean distance geometry is the study of Euclidean geometry based on the concept of distance. This is useful in several applications where the input data consists of an incomplete set of distances, and the output is a set of points in Euclidean space that realizes the given distances. We survey some of the theory of Euclidean distance geometry and some of the most important applications: molecular conformation, localization of sensor networks and statics.

1 Introduction

Distance Geometry studies Euclidean geometry through distances, centered on determining whether weighted graph data admit a realization in a specified Euclidean space. This survey develops foundational definitions and theory while emphasizing applications, especially protein-structure determination from NMR data.

1 Introduction: Distance Geometry originated with Menger’s distance-based characterizations, later completed by Blumenthal, and includes the subset problem of recognizing distance matrices.For Euclidean distances, Cayley’s results provide necessary conditions through vanishing Cayley-Menger determinants for suitably many points in lower-dimensional affine spaces.
1 Introduction: The Distance Geometry Problem asks whether a weighted graph admits a mapping x: V → R^K realizing its prescribed edge distances.A realization is such a mapping, while a realization of a subgraph is a partial realization of the full graph.
1 Introduction: The DGP connects classical distance geometry to sparse-distance positioning, where coordinates of geographically distributed objects are inferred from measurements for only some object pairs (Yemini,; [233]).Its applications include molecular conformation, wireless sensor networks, statics, data visualization, and robotics.
1 Introduction: The survey adopts an application-oriented perspective, focusing especially on determining protein structure from Nuclear Magnetic Resonance data.NMR measurements originate as frequency readings associated with distances between atom-type pairs, rather than directly as distance intervals.
1.1 Basic definitions: The mathematical preliminaries define weighted graphs, subgraphs, paths, cycles, chordality, minors, vertex orders, realizations, and rigidity-related concepts used throughout the survey.The survey also introduces PEO, DVOP, and Henneberg type I orders for graph-based realization algorithms.

2 The mathematics of distance geometry

This section develops Euclidean distance geometry through Cayley–Menger determinants, simplex orientation, exterior algebra, and matrix characterizations. It also connects these foundations to manifolds, semidefinite programming, and matrix completion.

Cayley–Menger determinants: Cayley–Menger determinants encode simplex volumes and oriented volumes, with opposite signs representing the two orientations of a simplex sharing a facet.They use pairwise distances duv = ∥pu − pv∥ and are connected to oriented matroids.
Manifolds: For curved manifolds, Gödel’s modification of the simplex condition extends distance geometry, including spherical realizations that relate it to kissing numbers and coding theory.The spherical result applies when a four-point set has a nonzero Cayley–Menger determinant.
Exterior algebra: Cayley–Menger determinants form an exterior-algebraic alternating product, where nonzero determinant is equivalent to linear independence and related invariants support chirotope realizations.The construction follows from identifying repeated-vector products with zero in the ideal generated by x^2.
PSD and matrix completion: Schoenberg’s bijection makes Euclidean distance matrices equivalent to positive semidefinite matrices: D represents points in R^K but not R^(K−1) exactly when x^⊤Ax is PSD of rank K [198].This correspondence underlies equivalent EDM and PSD matrix-completion problems.

3 Molecular Conformation

This section surveys molecular conformation as a primary application of distance geometry, emphasizing its role as an inverse problem connected to NMR-data interpretation and covering continuous, discrete, and interval-distance methods.

3 Molecular Conformation: Molecular conformation primarily uses distance geometry as an inverse problem connected to interpreting NMR data, though applications are not exclusive to this domain.The section covers continuous search methods, discrete search methods, extensions to interval distances, and recent NMR-specific results.

3.1 Test instances

Test instances span geometrical, physically motivated random, dense PDB, and sparse PDB constructions, with sparse PDB data preferred for NMR because measurements have a distance threshold. Methods are compared using realization accuracy and CPU time, with penalty, LDE, and RMSD as standard accuracy measures.

Test-instance choices: Test instances include geometrical models such as grids, physically motivated random models, dense PDB conformations [155, 3, 4], and sparse PDB conformations [83, 122].Dense PDB instances include within-residue distances and distances to neighboring residues, whereas sparse PDB instances include distances within a threshold.
Test-instance choices: Sparse PDB instances best match NMR testing because NMR measures distances only up to a given threshold.The survey therefore used mostly sparse PDB test sets, while occasionally adding geometric and hard random instances and avoiding easy dense PDB instances.
Test-instance choices: Dense PDB instances are considered easy because protein backbone order induces a 3-trilateration order in R3, given that residues contain more than three atoms.Graphs with such orders can be realized efficiently, limiting their usefulness as challenging test cases.
Evaluation measures: Methods are usually compared by the accuracy and speed of the realization x they produce, using accuracy measures and CPU time.Some methods, including BP, may additionally produce a whole set of valid realizations.
Evaluation measures: Penalty, Largest Distance Error (LDE), and Root Mean Square Deviation (RMSD) are the three popular accuracy measures.Penalty evaluates the objective function, LDE is a scaled averaged square-rooted penalty, and RMSD compares centered point sets after optimal rotations and translations; RMSD is meaningful when a known optimal configuration exists.

3.2 The Molecular Distance Geometry Problem

The Molecular Distance Geometry Problem (MDGP), equivalent to DGP3, models molecular conformation by recovering atom positions in R3 from incomplete Euclidean distances measured by NMR. This section reviews exact-distance solution methods, including global optimization, smoothing-based continuation, and geometric build-up algorithms.

3.2 The Molecular Distance Geometry Problem: The MDGP uses atoms as vertices and observed atom-pair distances as edges to determine molecular structure, namely relative atom positions in R3.NMR experiments provide a subset of short Euclidean distances, which the MDGP uses to recover compatible molecular conformations.
3.2 The Molecular Distance Geometry Problem: Numerical solution is difficult: fsolve failed on tiny weighted graphs with fewer than 10 vertices, while Couenne handled only instances with |V| ∈ {2, 3, 4} in reasonable time.The section formulates global optimization as minimizing squared infeasibility with a nonnegative fourth-degree polynomial objective, whose value is zero exactly on feasible realizations.
3.2 The Molecular Distance Geometry Problem: Gaussian-transform smoothing with homotopy continuation reduces local optima and supports effective MDGP optimization; DGSOL is efficient for small-to-medium instances and extends naturally to interval distances.DGSOL is freely available and was successfully tested on cubical grids, while Figure 3 contrasts a wrong 1mbn conformation from DGSOL with the correct one from BP Alg. 1.
3.2 The Molecular Distance Geometry Problem: The geometric build-up algorithm reconstructs vertices by triangulation from four non-coplanar neighbors, yielding a unique position when the required conditions hold.The method is designed for sufficiently dense graphs, and uniqueness follows because the associated linear system has a unique solution.
3.2 The Molecular Distance Geometry Problem: Updated geometric build-up controlled numerical error on 10 sparse PDB proteins, achieving RMSD from O(10^-8) to O(10^-13), while complete rational graphs admit linear-time O(n) solution.The original geometric build-up method is highly sensitive to numerical errors [64], motivating the updated algorithm proposed by Wu and Wu.

3.3 Discretizability · 3.3.1 Rigid geometry hypothesis and molecular graphs · 3.3.2 Development of the Branch-and-Prune algorithm

The section characterizes discretizable DGP instances through rigidity and develops Branch-and-Prune, an exact combinatorial search that exploits binary placements and pruning. It also explains molecular-graph construction and BP’s development for protein-conformation applications.

3.3 Discretizability: Discretizability supports accurate and efficient mixed-combinatorial methods, including an exact algorithm for finding all solutions of discretizable DGP instances.The discussion focuses on the relationship between discretizability, rigidity, and combinatorial search.
3.3 Discretizability: For a rigid graph, the realization set X is finite, whereas almost all non-rigid graphs with realizations have uncountably many solutions [16, Thm. 2.2.1; 153].Thus, rigidity reduces the search from a potentially uncountable space to finitely many realizations.
3.3 Discretizability: With the first K vertices fixed, a non-uniquely rigid graph offers two placements for each successive vertex, yielding |X| = 2^(n−K) before additional edges prune infeasible branches.Additional edges can eliminate one or both candidate placements.
3.3.2 Development of the Branch-and-Prune algorithm: Protein-backbone realization motivates non-uniquely rigid graphs because it is a difficult step toward realizing whole proteins, while backbone ordering can support exact BP.The natural atomic ordering can be exploited to construct vertex orders with exactness guarantees.
3.3.1 Rigid geometry hypothesis and molecular graphs: Known covalent bond lengths and bond angles determine distances between atoms separated by two bonds, completing the bond graph into the molecular graph G2 [99].The completion adds weighted edges whenever a two-edge path connects the atoms.
3.3.2 Development of the Branch-and-Prune algorithm: BP combines three-sphere intersections with a theoretically justified vertex order; conceived and validated in 2005, it appeared in 2008 and later proved complete on defined DGP subclasses [118, 124, 122, 159].Subsequent work also automated vertex ordering, adapted BP to proteins, compared methods, and reduced tree sizes through backbone decomposition.

3.3.3 Sphere intersections and probability · 3.3.4 The Discretizable Vertex Ordering Problem

Sphere intersections are governed by affine independence and simplex inequalities: generically, feasible intersections contain two points, while degenerate cases yield zero, one, or uncountably many. These facts motivate the DVOP, which seeks an ordering enabling at most 2^(n−K) realizations and is NP-complete in general but polynomial for fixed K.

3.3.3 Sphere intersections and probability: Simplex inequalities ∆K(U) ≥ 0, expressed using squared distances, characterize feasibility; strict inequalities imply two intersection points [115].The Cayley-Menger determinant provides the relevant distance-based condition, and sphere intersections receive detailed treatment in molecular modelling.
3.3.3 Sphere intersections and probability: If CM(U−) = 0, the sphere intersection is uncountable; if ∆K(U, d) = 0, it has one point; otherwise it has zero or two points [115].When the centers’ affine dimension is below K−1, the intersection is uncountable; otherwise its cardinality is in {0, 1, 2}.
3.3.3 Sphere intersections and probability: With probability 1, a nonempty intersection of K spheres with affinely independent centers has exactly two points; zero- and one-point cases are measure-zero degeneracies.If at least K adjacent predecessors exist in the ordering, infeasibility can reduce the number of realizations to at most 2^(n−K).
3.3.4 The Discretizable Vertex Ordering Problem: A valid vertex order with exactly K adjacent predecessors for every later vertex yields |X| = 2^(n−K) with probability 1.With at least K adjacent predecessors, either or both candidate positions may violate additional distances, so |X| can be smaller.
3.3.4 The Discretizable Vertex Ordering Problem: The DVOP seeks an ordering whose first K vertices form a K-clique and every later vertex has at least K adjacent predecessors, ensuring the initial realization is unique.The first K vertices must induce a clique because discretizable distance geometry problems require their realization to be known.
3.3.4 The Discretizable Vertex Ordering Problem: The DVOP is NP-complete, but enumerating K-subsets and greedily extending promising cliques gives an O(n^(K+3)) algorithm, hence polynomial time when K is fixed.The algorithm stops when the largest available number of adjacent predecessors falls below K.
3.3.4 The Discretizable Vertex Ordering Problem: DVOP preprocessing can sometimes solve sparse PDB instances whose backbone order is not a DVOP order, particularly when the distance threshold is 5.5Å rather than 6Å.The reported computational results associate this effect with using lower-than-usual thresholds.

3.3.5 The Discretizable Distance Geometry Problem

The Discretizable Distance Geometry Problem (DDGP) specifies a weighted graph, dimension parameter K, vertex order, and an initial realization, then asks whether the realization extends validly [115]. Its structural conditions enable sequential realization, while DDGP methods may also solve broader instances lacking an a priori characterization.

Problem definition: The DDGP input comprises a weighted undirected graph, an integer K > 0, an ordered vertex set, and a valid realization of the first K vertices.Each vertex after the first K has at least K adjacent predecessors.
Problem definition: For every vertex after the first K, K adjacent predecessors form a clique and satisfy strict triangular inequalities ∆K−1(Uv, d) > 0.These conditions define the predecessor subset Uv used for sequential realization.
Problem definition: The DDGP asks whether the initial realization can be extended to a valid realization of the graph, with fixed-dimensional variants denoted DDGPK and DDGP3 discussed in [159].The general decision problem is referenced in [115].
Scope and limitation: DDGP methods can solve additional instances even when the predecessor subgraph is not a graph clique, because current realizations can make ∆K−1(Uv, d) well defined during computation.No a priori characterization of these broader instances is currently available.

3.3.6 The Branch-and-Prune algorithm

The Branch-and-Prune algorithm recursively enumerates valid realizations by branching on sphere intersections and pruning infeasible candidates. It can find either all incongruent realizations or a single realization, with strong efficiency and reliability on sparse PDB instances.

The Branch-and-Prune algorithm: BP branches over at most two sphere-intersection candidates and finds the complete set X of valid realizations modulo rotations and translations.The algorithm is initialized by calling BP(K + 1, x̄, ∅).
The Branch-and-Prune algorithm: Each realization can be encoded by a binary sequence χ(x), whose signs indicate which side of the hyperplane through the predecessor embedding contains each vertex; this is called chirality.The initial K entries are fixed to 1, and the zero case has probability 0.
The Branch-and-Prune algorithm: BP can run to termination for all valid realizations or stop at the first leaf to obtain one realization, outperforming most tested continuous-search algorithms in efficiency and reliability.The passage characterizes BP as, to the authors’ knowledge, the only method that is…
The Branch-and-Prune algorithm: 25 sparse PDB instances yielded complete realization sets, each containing one realization with RMSD at worst O(10−6) and isomers with LDE at worst O(10−7), while total user CPU time was 5.87s.The instances ranged from n = 57, m = 476 to n = 3861, m = 35028; one outlier consumed 90% of the total time.
The Branch-and-Prune algorithm: Pruning edges reduce the BP search tree through Direct Distance Feasibility, potentially leaving zero or one candidate instead of two.Discretization edges ensure the instance belongs to the DDGP, while pruning edges test compatibility with their distances.

3.3.7 Dual Branch-and-Prune

Dual branch-and-prune completes partial Euclidean distance matrices by branching on up to two missing distances, continuing through cliques, and pruning non-Euclidean completions. It is dual to primal branch-and-prune through the correspondence between weighted graphs and partial symmetric matrices, and is complete by Theorem 3.1 ([137]).

3.3.7 Dual Branch-and-Prune: Dual branch-and-prune is the matrix-completion counterpart of primal branch-and-prune, linked by linear-time mappings between weighted graphs and partial symmetric matrices.The primal method chooses point realizations, whereas the dual method chooses missing distances.
3.3.7 Dual Branch-and-Prune: At each step, dual branch-and-prune assigns a missing distance using the Cayley–Menger equation of a K+2-vertex near-clique.The equation has at most two real candidate values when the partial matrix is a distance matrix, and no candidates when it has no Euclidean completion.
3.3.7 Dual Branch-and-Prune: The method branches when a missing distance has two feasible values, continues across full cliques, and prunes branches without a Euclidean completion.Near-cliques with one missing edge generally yield two realizations in R^K, while full cliques require no branching.
3.3.7 Dual Branch-and-Prune: Dual branch-and-prune returns all possible completions of the input partial distance matrix.Theorem 3.1 ([137]) establishes this completeness guarantee for Algorithm 2.
3.3.7 Dual Branch-and-Prune: Unlike primal branch-and-prune, the dual method requires an initial (K+1)-clique because a complete distance matrix represents two reflected realizations.The primal method requires only an initial K-clique.

3.3.8 The Discretizable Molecular Distance Geometry Problem

The DMDGP restricts each vertex’s predecessors to the K immediate predecessors, a structure motivated by protein-backbone realization and enabling theoretical results on symmetry, tractability, and complexity. It also admits a mathematical-programming formulation based on torsion-angle cosines.

Definition and motivation: The DMDGP requires each vertex’s K predecessors to be immediate predecessors, unlike the DDGP’s arbitrary predecessors, and generalizes to the KDMDGP for arbitrary K.Its discretization edges satisfy |u − v| ≤ K, with x(Uv) = {xv−K, . . . , xv−1}.
Definition and motivation: Protein molecular structure guarantees two immediate predecessors for each vertex v > 3, but this directly ensures discretizability only for K = 2.Additional protein properties yield a different vertex order satisfying the DMDGP definition.
Theoretical consequences: The immediate-predecessor structure supports symmetry results for X and fixed-parameter tractability of the BP algorithm on protein-backbone KDMDGPs with NMR data.The DMDGP is NP-hard by reduction from Subset-Sum [122], and this result generalizes to the KDMDGP.
Mathematical-programming formulation: A mathematical-programming formulation models each choice using torsion angles φv, whose input cosines cv constrain adjacent plane-normal scalar products.For v > 3, the formulation imposes αv−1(x) · αv(x) = ∥αv−1(x)∥∥αv(x)∥cv; fixed-K generalizations use Graßmann-Plücker relations.

3.3.9 Symmetry of the solution set

For KDMDGP instances, partial reflections form an Abelian symmetry group acting transitively on the solution set, proving that |X| is a power of two with probability 1. These symmetries also accelerate BP by generating all realizations from one found solution.

3.3.9 Symmetry of the solution set: Although early experiments found powers of two for protein and protein-like instances, a constructed instance had 54 solutions, while the probability-one theorem admits an infinite countable class of counterexamples [122, 145].The result explains the empirical conjecture while providing the foundation for a theory of partial reflections.
3.3.9 Symmetry of the solution set: Each BP branching pair consists of realizations related by reflection through the hyperplane defined by the K immediate predecessors.These partial reflections are injective and idempotent with probability 1, and their actions correspond to chirality transformations.
3.3.9 Symmetry of the solution set: With probability 1, the discretization group is an Abelian group isomorphic to C_2^(n−K), and its action on X is transitive.Its generators are commuting partial reflections that preserve discretization-edge distances and connect every realization.
3.3.9 Symmetry of the solution set: With probability 1, the pruning group acts transitively on X, implying |X| = 2^ℓ for some integer ℓ.The proof uses the pruning group as a subgroup of the discretization group, whose order is a power of two.
3.3.9 Symmetry of the solution set: Empirically, once BP finds one valid realization, group generators generate all other realizations up to rotations and translations, reducing CPU time to roughly 2/|X| [157, 158].The generators are available when the first valid realization is identified; the factor 2 reflects an existing reflection symmetry in BP.

3.3.10 Fixed parameter tractability

The paper establishes sufficient pruning-edge conditions under which the BP algorithm has fixed-parameter tractability and polynomial running time on protein instances. Empirically, 40 of 45 PDB proteins satisfy one condition and 5 satisfy another, all with v0 = 4.

3.3.10 Fixed parameter tractability: If sufficiently late vertices have pruning edges from earlier vertices, Proposition 3.9 bounds BP search-tree width by 2^(v0−K).The condition requires some v0 > K such that every v > v0 has a pruning edge {u, v} with u < v − K.
3.3.10 Fixed parameter tractability: If long pruning-edge-free subsequences are preceded by suitable pruning edges, Proposition 3.10 also bounds BP search-tree width by 2^(v0−K).Each qualifying predecessor must satisfy both a sufficient separation condition and an incident pruning edge.
3.3.10 Fixed parameter tractability: Under the first two conditions, BP has worst-case running time O(2^v0 n) when computing T has complexity typically constant in n [140].The general width bound is O(2^v0 log n), yielding O(2^v0 L^2 log n) = O(Ln) before treating L as constant.
3.3.10 Fixed parameter tractability: A weaker condition allowing logarithmically many exceptional power-of-two levels gives width at level n bounded by 2^v0 n and running time O(2^v0 n^2).The associated pruning-edge path follows the diagonal except at those exceptional levels, where the number of search nodes doubles.
3.3.10 Fixed parameter tractability: 40 of 45 PDB protein instances satisfy Proposition 3.9 and 5 satisfy Proposition 3.10, all with v0 = 4, supporting linear empirical complexity [140, 122].The results are consistent with computational evidence that BP displays polynomial, specifically linear, complexity on real proteins.

3.4 Interval data

Interval distance geometry models uncertain NMR measurements as distance intervals and seeks embeddings satisfying nonlinear inequality constraints. The section surveys smoothing, projection, basin-hopping, multilevel, and stochastic methods for this problem.

Interval data represent NMR measurement uncertainty, turning prescribed distances into real-valued bounds that embeddings must satisfy through nonlinear inequalities.The interval formulation replaces exact edge distances with intervals [dL, dU].
Other approaches adapt smoothing methods, complete and refine bounds before matrix decomposition in EMBED, or use monotonic basin hopping and multilevel local NLP searches.These methods address the interval formulation through distinct combinations of bound refinement, local optimization, and structured search.
Hyperbolic smoothing improves computational results by matching the summand shape, but performs best for near-cubic grid arrangements.Its algorithm is close to DGSOL, while its problem-specific smoothing distinguishes it from general-purpose Gaussian smoothing.
Alternating projections repeatedly project a randomly initialized pre-distance matrix onto negative-semidefinite and zero-diagonal convex sets to seek a Euclidean distance matrix.Although worst-case convergence may require infinitely many iterations, empirical tests suggest five APA iterations are sufficient, including on a 588-atom protein.
Stochastic Proximity Embedding randomly moves atom pairs when interval constraints are violated, but offers no guarantee of satisfying all constraints.Reported “success stories” in nevertheless support it as a valid methodology.

3.5 NMR data

NMR experiments provide incomplete, interval-valued distance information, mainly for hydrogen pairs, but ambiguity and experimental errors limit reliability. Protein-specific re-orders and interval branch-and-prune methods use chemically known distances for discretization while reserving NMR intervals primarily for pruning.

NMR measurements: NMR data estimate distances for selected atom pairs, mostly hydrogens, but indistinguishable atoms require pseudo-atoms and progressively enlarged upper bounds.Signals can also be affected by molecular instability, machine noise, and spin diffusion, while manipulation of observations introduces interval-type errors [17].
NMR measurements: Known molecular composition supplements NMR with covalent-bond distances, two-bond distances, and atom identities, enabling chemically informed distance-geometry models.NMR observations are commonly represented as triplets ({a, b}, d, q), with exact distances replaced by intervals after error-prone processing.
Re-orders: Re-orders address unreliable non-hydrogen NMR distances by exploiting hydrogen atoms, repeated atoms, and finite candidate sets replacing torsion-angle intervals [123, 170].They let atoms of valence greater than two contribute multiple bond lengths and make torsion-derived intervals tightly discretizable without loss of precision.
Interval BP: The interval BP algorithm replaces spheres with spherical shells when intersecting distance constraints, while retaining branching and pruning phases for interval data.In three dimensions, intersecting two spheres with a spherical shell yields, with probability one, two disjoint curves.
Interval BP: Using re-orders, precise chemically derived distances perform discretization and NMR intervals are used only for pruning, producing search-tree nodes with at most 2D subnodes.The search tree is therefore no longer binary when a discretizable interval is branched on.
Protein side chains: Applying discretization to complete protein conformations remains difficult because side chains have complex, potentially large structures across all 20 amino acids.Side chains are nevertheless important for identifying protein conformations.

4 Engineering applications

Engineering applications of distance geometry include wireless sensor-network localization, statics, data visualization, and robotics. The supplied material emphasizes localization through global rigidity, unique localizability, and scalable SDP-based formulations.

4.1 Wireless networks: Wireless sensor-network localization uses pairwise sensor-distance estimates to recover positions needed for routing communication signals.The relevant setting is typically R^2 or R^3, including multilayer buildings and mountainous regions.
4.1 Wireless networks: Global rigidity means that a graph has a realization unique up to congruence, and it determines when sensor positions are uniquely recoverable.For K=2, global rigidity is characterized by the 2- or 3-clique cases, or by 3-connectivity and redundant rigidity.
4.1 Wireless networks: K-unique localizability enables exact polynomial-time realization through SDP duality, provided uniqueness holds in R^K and higher dimensions and anchors ensure global rigidity.The anchor subgraph must be generically globally rigid and contain at least K + 1 anchors; the exact algorithm is described in.
4.1 Wireless networks: SDP methods dominate recent wireless-localization approaches because they connect distance geometry with semidefinite feasibility and can accommodate interval-valued, imprecise distances.Facial reduction and vertex clustering improve SDP scaling by identifying cliques and expanding them through K-trilateration orders.
4.1 Wireless networks: The SOCP relaxation scales to 4000 vertices versus 500 for the SDP relaxation, while the stronger ESDP relaxation has similar scaling.The SOCP constraint relaxes ∥w_uv∥2 = y_uv to ∥w_uv∥2 ≤ y_uv; Tseng abandoned it in favor of ESDP.
4.2 Statics and rigidity: In R^2, Laman’s characterization gives rigid graphs with |E| = 2|V|−3 and |E′| ≤ 2|V′|−3 for every subgraph, whereas no complete characterization is known for K > 2.Rigidity and infinitesimal rigidity coincide across generic frameworks, allowing rigidity to be treated as a graph property in almost all cases [7, 8].

5 Conclusion

Euclidean distance geometry is a mature, extensive field with major biological, statistical, and engineering applications. Recent extensions address the inverse problem of determining a distance space from a partial distance function, adding mathematical and applied interest.

Euclidean distance geometry has major applications in biology, statistics, and engineering.
Its theoretical foundations were established around a century ago by Cayley, Menger, Schoenberg, Blumenthal, and Gödel.
Recent extensions study the inverse problem of determining a distance space from a partial distance function.These extensions contribute further mathematical and applied interest to the field.