0
$\begingroup$

Given a simplex of $N$ points $x$, or a general convex hull $C$, and a point $a \in C$. Find a barycentric coordinates of $a$ given $N-1$ bisections of edges of the convex hull $[x_i,x_j]$ for $i \neq j$, where bisecting point is the projection of $a$ to $[x_i,x_j]$

Assume that there are $N$ points $x_n$ in some possibly infinite-dimensional Hilbert space $H$. For simplicity assume $0 = a \in C = \mathrm{conv}\{ x_n \}^N_{n =1}$, where $\mathrm{conv}(A)$ is the convex hull, which is the set of all convex combinations of points in the set $A$. Assume additionaly that $x_n$ are convexly independent. That is, for each unit simplex point $$\lambda \in \triangle^N = \left\{ \lambda \in \mathbb{R}^N_{+} : \sum^N_{n = 1} \lambda_n = 1 \right\},$$ such that $\sum^N_{n = 1} \lambda_n x_n = x_i$, the point $\lambda$ is in James boundary of $\triangle^N$, which means that $\lambda_j = \delta_{i,j}$, where $\delta_{i,j}$ is the Kronecker delta. Then, there is a unique $r \in \triangle^N$ such that $\sum^N_{n = 1} r_n x_n = 0$. $r$ are barycentric coordinates of $a$. Assume for simplicity that $r > 0$, that is $a$ lies in the relative interior of $C$.

For $i \neq j$ the edge $$[x_i, x_j] = \left\{ \lambda_1 x_i + \lambda_2 x_j |\lambda \in \triangle^2 \right\}$$ the problem is to find a projection a projection of $0$ to $[x_i,x_j]$. Denote it by $\pi_{i,j} a$.

Some simple computations show that (under assumption $a = 0$) $$ \pi_{i,j} 0 = \frac{\| x_i \|^2 - \langle x_i , x_j \rangle }{ \| x_i \|^2 + \| x_j \|^2 - 2 \langle x_i, x_j \rangle}x_j + \frac{\| x_j \|^2 - \langle x_i , x_j \rangle }{ \| x_i \|^2 + \| x_j \|^2 - 2 \langle x_i, x_j \rangle}x_i $$ However, it would be convenient to have above expression in the values of $r_n$.

For example, consider a problem: given values for $\pi_{i,i + 1}0$ restore value of $r$. This problem must be feasible, as both are $N - 1$ coordinates, however I do not know how to address it.

$\endgroup$
  • $\begingroup$ I find it difficult to understand the formulation of the problem. Is $C$ contained in the affine hull of the $N$ points $x_k$? $\endgroup$ – copper.hat May 19 '17 at 16:17
  • $\begingroup$ $C$ is a convex hull of points $x_k$, so yes it is. The problem is finite dimensional in fact. $\endgroup$ – Nik Pronko May 19 '17 at 16:36
  • $\begingroup$ Perhaps you can use the fact that $a = x_n+\sum_{k<n} \lambda_k (x_k-x_n)$ $\endgroup$ – copper.hat May 19 '17 at 18:53
  • $\begingroup$ I don't really see how you can do this with just projections onto the edges without additional structure. It seems to me you need to compute the inverse of a matrix $[Q]_{ij} = 1+ \langle x_i, x_j \rangle$ times a column vector of the form $[v]_k = 1 + \langle x_i, a\rangle$. $\endgroup$ – copper.hat May 20 '17 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.