Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If you have the $||a_i||$ as well, you could use the polarization identity to get the inner product from which the desired norm follows. Since translation doesn't matter for the value of $||p-q||$, we could just suppose that $a_1=0$ and then you can figure out the rest... –  copper.hat Jul 13 '12 at 23:14
    
@copper.hat Um sorry but I'm confused. The inner product dealt here is the usual inner product given in $\mathbb{R}^n$ so there is no need to "get the inner product". If by polarization identity you are referring to $||\textbf{x}||^2+||\textbf{y}||^2=\frac12(||\textbf{x-y}||^2+||\textbf{x+y}||^2‌​)$, I can't see how it relates the barycentric coordinates of two given points to distances between them. Also, as far as I know, figuring out coordinates of a simplex from distances between the vertices is a quite complicated problem. –  progressiveforest Jul 13 '12 at 23:30
    
Unless I am missing something, it is straightforward. See below. –  copper.hat Jul 13 '12 at 23:39

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer
    
Thanks for the edit @J.M. –  copper.hat Jul 14 '12 at 4:21
    
Thanks a lot! Embarassingly I never considered writing the distance squared as a dot product. –  progressiveforest Jul 14 '12 at 15:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.