---
tag: B83KZW70C8
kind: definition
name: Distance geometry
msc: [51K05, 51K99]
defines: HPW5F0GQ4B
uses: [0JD5C82QMB, 0C95TG69SG]
sources:
  - url: https://en.wikipedia.org/wiki/Distance_geometry
---

## Definition

Let $G = (V, E)$ be a finite [[graph|0JD5C82QMB]], let $\delta \colon E \to [0, \infty)$ be a weight on its edges, and let $k \ge 1$ be an integer.
A *realization* of $(G, \delta)$ in $\R^k$ is a map $p \colon V \to \R^k$ such that
$$\norm{p(u) - p(v)} = \delta(uv) \quad \text{for every edge } uv \in E.$$
Here $\norm{p(u) - p(v)}$ is the [[Euclidean distance|0C95TG69SG]] of the two points.
The *distance geometry problem* asks, for given $(G, \delta)$ and $k$, whether a realization in $\R^k$ exists, and to find one.
Distance geometry is the study of such realizations and of the point sets they describe.

## Remarks

Example: let $G$ be a triangle with edge weights $3$, $4$ and $5$, and $k = 2$.
The points $(0, 0)$, $(3, 0)$ and $(3, 4)$ form a realization, since their pairwise distances are $3$, $4$ and $5$.

Non-example: the same triangle with weights $1$, $1$ and $3$ has no realization in any $\R^k$, since $3 > 1 + 1$.

When $G$ is a complete graph, a realization exists in some $\R^k$ if and only if the squared weights form a [[Euclidean distance matrix|1BCJ7A73KS]].
A realization is never unique: an isometry of $\R^k$ moves it to another one.