1
$\begingroup$

Assume that we are given every distance between each pair of points from a $n$-simplex $\triangle$. Given $n$-dimensional barycentric coordinates (measured with respect to $\triangle$) of two points, how do we compute the distance between the two points?

A more detailed explanation of the question is given below:

Given $n+1$ vectors $\{\mathbf{a}_1,\cdots,\mathbf{a}_{n+1}\}$ from $\mathbb{R}^n$, we can give homogeneous coordinates to another vector $\mathbf{x}\in\mathbb{R}^{n+1}$ as $(\lambda x_1:\lambda x_2:\cdots:\lambda x_n)$ where $\lambda\in\mathbb{R}-\{0\}$ and $\mathbf{x}={(\sum x_i \mathbf{a}_i)}/{(\sum x_i)}$. $x_i$ can be alternatively defined as the volume of the simplex formed by vectors $\{\mathbf{x},\mathbf{a}_1, \cdots, \mathbf{a}_{i-1},\mathbf{a}_{i+1},\cdots,\mathbf{a}_{n+1}\}$ (which can be computed via Cayley-Menger determinant, I believe.)

Assume that we are given matrix $M$ such that $M_{ij}=\|\mathbf{a}_i-\mathbf{a}_j\|^2$, i.e. we are given the distances between arbitrary two points from $\{\mathbf{a}_1,\cdots,\mathbf{a}_{n+1}\}$. If we are given barycentric coordinates $P,Q\in\mathbb{R}^{n+1}$ of two vectors $\mathbf{p},\mathbf{q}\in\mathbb{R}^n$, can we express $\|\mathbf{p}-\mathbf{q}\|^2$ in terms of $P,Q,M$?

This is already answered for $n=1,2$. For $n=1$ it is trivial. For $n=2$, assuming that $P$ and $Q$ are normalized (that is, their coordinate sums are equal to 1), and $P=\{p_1:p_2:p_3\},Q=\{q_1:q_2:q_3\}$, distance $\|\mathbf{p}-\mathbf{q}\|^2=\sum_{cyc}\frac12(-a^2+b^2+c^2)(p_1-q_1)^2$ where $a,b,c$ are sidelengths of the simplex.

  • 0
    Unless I am missing something, it is straightforward. See below.2012-07-13

1 Answers 1

3

Suppose $p = \sum_i \pi_i a_i$, $q = \sum_i \zeta_i a_i$, with $\sum_i \pi_i = \sum_i \zeta_i = 1$. Then $\|p-q\| = \| \sum_i (\pi_i - \zeta_i) a_i\|$. Then we can express the norm as $\|p-q\|^2 = \sum_{i,j} (\pi_i - \zeta_i)(\pi_j-\zeta_j) \langle a_i, a_j \rangle$. So we just need to figure out the $\langle a_i, a_j \rangle$.

Suppose we let $\hat{a}_i = a_i -a_1$. Then since $\sum_i (\pi_i - \zeta_i) a_1 = 0$, we have that $p-q = \sum_i (\pi_i - \zeta_i) \hat{a}_i$. Furthermore, since $a_i-a_j = \hat{a}_i - \hat{a}_j$, the matrix $M$ gives us the distances $\|\hat{a}_i - \hat{a}_j\|$. Since $\hat{a}_1 = 0$, we have $\|\hat{a}_i\|^2 = M_{1i}$

We need to compute $\|p-q\|^2 = \sum_{i,j} (\pi_i - \zeta_i)(\pi_j-\zeta_j) \langle \hat{a}_i, \hat{a}_j \rangle$.

The polarization identity gives the inner product as (note the minus sign) $-\langle x , y \rangle = \frac{1}{2} ( \|x-y\|^2-\|x\|^2-\|y\|^2),$ from which we have $\langle \hat{a}_i, \hat{a}_j \rangle = -\frac{1}{2}(M_{ij} - M_{i1}-M_{j1})$.

Consequently, $\|p-q\|^2 = - \frac{1}{2} \sum_{i,j} (\pi_i - \zeta_i)(\pi_j-\zeta_j) (M_{ij} - M_{i1}-M_{j1})$.

This can be written as $- \frac{1}{2} \langle \pi-\zeta, B(\pi-\zeta) \rangle$, where $B = M - M_{\cdot 1} 1^T - 1^T M_{1 \cdot}$, where $1$ is a vector of $1$'s, $M_{\cdot 1}$ represents the first column of $M$, and $M_{1 \cdot}$ represents the first row of $M$ (these last two vectors are transposes of each other, of course).

  • 0
    Thanks a lot! Embarassingly I never considered writing the distance squared as a dot product.2012-07-14