Notation:
- $p_{i, j, k}$; the $k^{th}$ component of the $j^{th}$ boundary coordinate on the $i^{th}$ boundary
Finding a weight in 2D
I have 2 sets of 2 boundary coordinates in $\mathbb{R}^2$ space. The boundaries and their coordinates are indicated in green in Figure 1 below. Corresponding coordinates in each set are tied together by a line (a tie-line or tie-1-simplex). The tie-1-simplices are indicated in solid red in Figure 1.
$\mathbb{R}^2$" />
In each set ($i$), I can create a vector; $\bar{v}_i = p_{i, 2} - p_{i, 1} \quad :i \in \mathbb{N} [1, 2]$
A point on a vector can be described by the two coordinates and a weight; $r_i(p_{i, 1}, p_{i, 2}, \beta) = p_{i,1} + \beta \bar{v}_i = p_{i,1}+ \beta(p_{i,2} - p_{i,1}) \quad :\beta \in \mathbb{R} [0, 1]$
Within the convex hull of these coordinates I have another target coordinate; $p_t$, indicated in blue in Figure 1.
A simplex of $\mathbb{R}^1$ (a line), indicated in hashed red in Figure 1, exist in this $\mathbb{R}^2$ space that contains the target coordinate and whose vertices are found on each of the vectors where the weight $\beta$ is the same for both vectors.
Given the sets of boundary coordinates and target coordinate, how can I explicitly calculate $\beta$. An iterative method is to be avoided as this calculation is critical to the performance of an algorithm.
Finding a weight in 3D. Case 1
This is very similar to the 2D case.
I have 3 sets of 2 boundary coordinates in $\mathbb{R}^3$ space. The boundaries and their coordinates are indicated in green in Figure 2 below. Corresponding coordinates in each set are tied together by a triangle (a tie-triangle or tie-2-simplex). The tie-2-simplices are indicated in solid red in Figure 2.
$\mathbb{R}^3$" />
In each set ($i$), I can create a vector; $\bar{v}_i = p_{i, 2} - p_{i, 1} \quad :i \in \mathbb{N} [1, 3]$
A point on a vector can be described by the two coordinates and a weight; $r_i(p_{i, 1}, p_{i, 2}, \beta) = p_{i,1} + \beta \bar{v}_i = p_{i,1}+ \beta(p_{i,2} - p_{i,1}) \quad :\beta \in \mathbb{R} [0, 1]$
Within the convex hull of these coordinates I have another target coordinate; $p_t$, indicated in blue in Figure 2.
A simplex of $\mathbb{R}^2$ (a triangle), indicated in hashed red in Figure 2, exist in this $\mathbb{R}^3$ space that contains the target coordinate and whose vertices are found on each of the vectors where the weight $\beta$ is the same for both vectors.
Given the sets of boundary coordinates and target coordinate, how can I explicitly calculate $\beta$. An iterative method is to be avoided as this calculation is critical to the performance of an algorithm.
Finding a weight in 3D. Case 2
Similar to the first 3D case where the boundaries were lines (one vector per boundary), in this case the boundaries are surfaces defined by three coordinates (two vectors per boundary).
I now have 2 sets of 3 boundary coordinates in $\mathbb{R}^3$ space. The boundaries and their coordinates are indicated in green in Figure 3 below. Corresponding coordinates in each set are tied together by a line (a tie-line or tie-1-simplex). The tie-1-simplices are indicated in solid red in Figure 3.
$\mathbb{R}^3$" />
In each set ($i$), I can create two vectors, each originating from the same coordinate (coordinate 1 for instance); $\bar{v}_{i, 12} = p_{i, 2} - p_{i, 1}, \bar{v}_{i, 13} = p_{i, 3} - p_{i, 1} \quad :i \in \mathbb{N} [1, 2]$
With these two vectors, I can describe a coordinate on the surface created between them. A point on the surface can be described by the three coordinates and two weights; $r_i(p_{i, 1}, p_{i, 2}, p_{i, 3}, \beta_1, \beta_2) = p_{i,1} + \beta_1 \bar{v}_{i, 12} + \beta_2 \bar{v}_{i, 13} = p_{i,1}+ \beta_1(p_{i,2} - p_{i,1}) + \beta_2(p_{i,3} - p_{i,1}) \quad :\beta_i \in \mathbb{R} [0, 1]; \beta_i >= 0; \Sigma{\beta_i} <= 1$
Within the convex hull of these coordinates I have another target coordinate; $p_t$, , indicated in blue in Figure 3.
A simplex of $\mathbb{R}^1$ (a line), indicated in hashed red in Figure 3, exist in this $\mathbb{R}^3$ space that contains the target coordinate and whose vertices are found on each of the surfaces described by the two sets of vectors where the weights $\beta_i$ and $\beta_2$ are the same for each surface.
Given the sets of boundary coordinates and target coordinate, how can I explicitly calculate $\beta_1$ and $\beta_2$. An iterative method is to be avoided as this calculation is critical to the performance of an algorithm.
Finding a weight in generic case
I would ultimately like to get to the point where I can calculate any number of $\beta$ weights in $\mathbb{R}^n$.
Is there someone that has solved a similar problem before or has a suggestion on how this can be attempted? I would appreciate it.
I have found an expression that can be used to determine the $\beta$ values, but unfortunately it is not an explicit solution but can be solved with non-linear methods. I have shown below how I derived the solution for each case, referring to some expressions in the question. This was done to show where I got the pattern shown in the generic solution.
Notation:
Finding a weight in 2D
As indicated, a point on each boundary can be represented by the vector that connects the boundary coordinates and a weight, $\beta$;
$r_i(p_{i, 1}, p_{i, 2}, \beta) = p_{i,1} + \beta \bar{v}_i = p_{i,1}+ \beta(p_{i,2} - p_{i,1}) \quad :\beta \in \mathbb{R} [0, 1]$
This was expanded and factorised so that each boundary coordinate was expressed individually together with a weight;
$r_i(p_{i, 1}, p_{i, 2}, \beta) = p_{i,1}(1 - \beta) + p_{i,2}(\beta) \quad :\beta \in \mathbb{R} [0, 1]$
With the $\beta$ value equal for both boundaries, the two coordinates required to create the tie-simplex that contains the target coordinate, are known, albeit in terms of an unknown variable. These two coordinates can be used to create another vector, $\bar{t}$, that represents the tie-simplex;
$\bar{s} = r_{2} - r_{1}$
This vector $\bar{s}$, together with a tie-simplex weight, $\alpha$, can be used to express the target coordinate;
$t(r_{1}, r_{2}, \alpha) = r_{1} + \alpha \bar{s} = r_{1} + \alpha(r_{2} - r_{1}) \quad :\alpha \in \mathbb{R} [0, 1]$.
This was expanded and factorised so that each of the coordinates could be expressed individually together with a weight;
$t(r_{1}, r_{2}, \alpha) = r_{1}(1 - \alpha) + r_{2}(\alpha) \quad :\alpha \in \mathbb{R} [0, 1]$.
After substituting the expressions for $r_{1}$ and $r_{2}$, the target coordinate $t$, can be expressed in terms of the known boundary coordinates, the boundary weight $\beta$, and tie-simplex weight $\alpha$;
$t = r_{1}(1 - \alpha) + r_{2}(\alpha) = [p_{1,1}(1 - \beta) + p_{1,2}(\beta)](1 - \alpha) + [p_{2,1}(1 - \beta) + p_{2,2}(\beta)](\alpha) \quad :\alpha, \beta \in \mathbb{R} [0, 1]$
After some expanding and factorising, this can be written in matrix and vector notation as;
$\bar{t} = \bf{P}\bar{\omega}$
where
$\bar{t} = \begin{bmatrix} t_{x}\\ t_{y} \\ \end{bmatrix}$
$\bf{P} = \begin{bmatrix} p_{1, 1, x} & p_{1, 1, y} \\ p_{1, 2, x} & p_{1, 2, y} \\ p_{2, 1, x} & p_{2, 1, y} \\ p_{2, 2, x} & p_{2, 2, y} \\ \end{bmatrix} ^T$
$\bar{\omega} = \begin{bmatrix} (1 - \beta)(1 - \alpha) \\ (\beta)(1 - \alpha)\\ (1 - \beta)(\alpha) \\ (\beta)(\alpha)\\ \end{bmatrix} $
With the target coordinate known as well as all the boundary coordinates, this system of equations can be solved to obtain the boundary weight $\beta$. This however cannot be done with linear algebra seeing that this is a non-linear expression.
Finding a weight in 3D, case 1
As with the 2D case, a coordinate can be expressed with the following expression because there are only two coordinates that creates the 1D boundary;
$r_i(p_{i, 1}, p_{i, 2}, \beta) = p_{i,1}(1 - \beta) + p_{i,2}(\beta) \quad :\beta \in \mathbb{R} [0, 1]$
In this case however, there are three boundaries, and therefore three coordinates that creates the tie-simplex that contains the target coordinate. Two vectors can be created from one of the coordinates to the others;
$\bar{s}_1 = r_{2} - r_{1}$, and $\bar{s}_2 = r_{3} - r_{1}$
These vectors $\bar{s}_1$ and $\bar{s}_2$, together with two tie-simplex weights, $\alpha_1$ and $\alpha_2$, can be used to express the target coordinate;
$t(r_{1}, r_{2}, r_{3}, \alpha_1, \alpha_2) = r_{1} + \alpha_1 \bar{s}_1 + \alpha_2 \bar{s}_2 = r_{1} + \alpha_1(r_{2} - r_{1}) + \alpha_2(r_{3} - r_{1}) \quad :\alpha_1, \alpha_2 \in \mathbb{R} [0, 1]$.
This was expanded and factorised so that each of the coordinates could be expressed individually together with a weight;
$t(r_{1}, r_{2}, r_{3}, \alpha_1, \alpha_2) = r_{1}(1 - \alpha_1 - \alpha_2) + r_{2}(\alpha_1) + r_{3}(\alpha_2) \quad :\alpha_1, \alpha_2 \in \mathbb{R} [0, 1]$.
After substituting the expressions for $r_{1}$, $r_{2}$ and $r_{2}$, the target coordinate $t$, can be expressed in terms of the known boundary coordinates, the boundary weight $\beta$, and tie-simplex weights $\alpha_1$ and $\alpha_2$;
\begin{align} t &= r_{1}(1 - \alpha_1 - \alpha_2) + r_{2}(\alpha_1) + r_{3}(\alpha_2) \\ &= [p_{1,1}(1 - \beta) + p_{1,2}(\beta)](1 - \alpha_1 - \alpha_2) + [p_{2,1}(1 - \beta) + p_{2,2}(\beta)](\alpha_1) + [p_{3,1}(1 - \beta) + p_{3,2}(\beta)](\alpha_2) \\ & \alpha_1, \alpha_2, \beta \in \mathbb{R} [0, 1] \end{align}
After some expanding and factorising, this can be written in matrix and vector notation as;
$\bar{t} = \bf{P}\bar{\omega}$
where
$\bar{t} = \begin{bmatrix} t_{x} \\ t_{y} \\ t_{z} \\ \end{bmatrix}$
$\bf{P} = \begin{bmatrix} p_{1, 1, x} & p_{1, 1, y} & p_{1, 1, z}\\ p_{1, 2, x} & p_{1, 2, y} & p_{1, 2, z}\\ p_{2, 1, x} & p_{2, 1, y} & p_{2, 1, z}\\ p_{2, 2, x} & p_{2, 2, y} & p_{2, 2, z}\\ p_{3, 1, x} & p_{3, 1, y} & p_{3, 1, z}\\ p_{3, 2, x} & p_{3, 2, y} & p_{3, 2, z}\\ \end{bmatrix} ^T$
$\bar{\omega} = \begin{bmatrix} (1 - \beta)(1 - \alpha_1 - \alpha_2) \\ (\beta)(1 - \alpha_1 - \alpha_2)\\ (1 - \beta)(\alpha_1) \\ (\beta)(\alpha_1)\\ (1 - \beta)(\alpha_2) \\ (\beta)(\alpha_2)\\ \end{bmatrix} $
With the target coordinate known as well as all the boundary coordinates, this system of equations can be solved to obtain the boundary weight $\beta$. This however cannot be done with linear algebra seeing that this is a non-linear expression.
Finding a weight in 3D, case 2
In the first case of 3D, the boundaries were 1D with two boundary coordinates each. In this case, the boundaries are 2D with three boundary coordinates each.
As indicated, a point on each boundary can be represented by two vectors (with the same origin) and two boundary weights, $\beta_1$ and $\beta_2$;
$r_i(p_{i, 1}, p_{i, 2}, p_{i, 3}, \beta_1, \beta_2) = p_{i,1} + \beta_1 \bar{v}_{i, 12} + \beta_2 \bar{v}_{i, 13} = p_{i,1}+ \beta_1(p_{i,2} - p_{i,1}) + \beta_2(p_{i,3} - p_{i,1}) \quad :\beta_i \in \mathbb{R} [0, 1]$
This was expanded and factorised so that each of the coordinates could be expressed individually together with a weight;
$r_i(p_{i, 1}, p_{i, 2}, p_{i, 3}, \beta_1, \beta_2) = p_{i,1}(1 - \beta_1 - \beta_2) + p_{i,2}(\beta_1) + p_{i,3}(\beta_2) \quad :\beta_i \in \mathbb{R} [0, 1]$
Because there are only two boundaries in this case, the tie-simplex between the two boundaries can be expressed by a vector and single tie-simplex weight, $\alpha$, as in the 2D case (shown in expanded and factorised format);
$t(r_{1}, r_{2}, \alpha) = r_{1}(1 - \alpha) + r_{2}(\alpha) \quad :\alpha \in \mathbb{R} [0, 1]$.
After substituting the expressions for $r_{1}$ and $r_{2}$, the target coordinate $t$, can be expressed in terms of the known boundary coordinates, the boundary weights $\beta_1$ and $\beta_2$, and tie-simplex weight $\alpha$;
\begin{align} t &= r_{1}(1 - \alpha) + r_{2}(\alpha) \\ &= [p_{1,1}(1 - \beta_1 - \beta_2) + p_{1,2}(\beta_1) + p_{1,3}(\beta_2)](1 - \alpha) + [p_{2,1}(1 - \beta_1 - \beta_2) + p_{2,2}(\beta_1) + p_{2,3}(\beta_2)](\alpha) \\ &\alpha, \beta_1, \beta_2 \in \mathbb{R} [0, 1] \end{align}
After some expanding and factorising, this can be written in matrix and vector notation as;
$\bar{t} = \bf{P}\bar{\omega}$
where
$\bar{t} = \begin{bmatrix} t_{x} \\ t_{y} \\ t_{z} \\ \end{bmatrix}$
$\bf{P} = \begin{bmatrix} p_{1, 1, x} & p_{1, 1, y} & p_{1, 1, z}\\ p_{1, 2, x} & p_{1, 2, y} & p_{1, 2, z}\\ p_{1, 3, x} & p_{1, 3, y} & p_{1, 3, z}\\ p_{2, 1, x} & p_{2, 1, y} & p_{2, 1, z}\\ p_{2, 2, x} & p_{2, 2, y} & p_{2, 2, z}\\ p_{2, 3, x} & p_{2, 3, y} & p_{2, 3, z}\\ \end{bmatrix} ^T$
$\bar{\omega} = \begin{bmatrix} (1 - \beta_1 - \beta_2)(1 - \alpha) \\ (\beta_1)(1 - \alpha)\\ (\beta_2)(1 - \alpha)\\ (1 - \beta_1 - \beta_2)(\alpha) \\ (\beta_1)(\alpha)\\ (\beta_2)(\alpha)\\ \end{bmatrix} $
With the target coordinate known as well as all the boundary coordinates, this system of equations can be solved to obtain the boundary weight $\beta$. This however cannot be done with linear algebra seeing that this is a non-linear expression.
Finding weights in generic case
The boundaries and the tie-simplex should always be simplices. The tie-simplex can be of a different order as the boundaries, but all the boundaries should be of the same order.
Given the generic case where $B$ number of boundaries are found and is expressed by $C$ number of boundary coordinates each, in $N$ dimensions. When $C$ number of boundary coordinates are present, the number of boundary weights $\beta$ is equal to $C - 1$. If $B$ number of boundaries are present, the number of tie-simplex weights $\alpha$ is equal to $B - 1$.
$\bar{t} = \begin{bmatrix} t_{x} \\ t_{y} \\ t_{z} \\ \vdots \\ t_{N} \\ \end{bmatrix}$
$\bf{P} = \begin{bmatrix} p_{1, 1, x} & p_{1, 1, y} & p_{1, 1, z} & \dots & p_{1, 1, N}\\ p_{1, 2, x} & p_{1, 2, y} & p_{1, 2, z} & \dots & p_{1, 2, N}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ p_{1, C, x} & p_{1, C, y} & p_{1, C, z} & \dots & p_{1, C, N}\\ p_{2, 1, x} & p_{2, 1, y} & p_{2, 1, z} & \dots & p_{2, 1, N}\\ p_{2, 2, x} & p_{2, 2, y} & p_{2, 2, z} & \dots & p_{2, 2, N}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ p_{2, C, x} & p_{2, C, y} & p_{2, C, z} & \dots & p_{2, C, N}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ p_{B, C, x} & p_{B, C, y} & p_{B, C, z} & \dots & p_{B, C, N}\\ \end{bmatrix} ^T$
$\bar{\omega} = \begin{bmatrix} (1 - \Sigma \beta)(1 - \Sigma \alpha) \\ (\beta_1)(1 - \Sigma \alpha)\\ (\beta_2)(1 - \Sigma \alpha)\\ \vdots \\ (\beta_{C-1})(1 - \Sigma \alpha)\\ (1 - \Sigma \beta)(\alpha_1) \\ (\beta_1)(\alpha_1)\\ (\beta_2)(\alpha_1)\\ \vdots \\ (\beta_{C-1})(\alpha_1)\\ (1 - \Sigma \beta)(\alpha_2) \\ (\beta_1)(\alpha_2)\\ (\beta_2)(\alpha_2)\\ \vdots \\ (\beta_{C-1})(\alpha_2)\\ \vdots \\ (1 - \Sigma \beta)(\alpha_{B-1}) \\ (\beta_1)(\alpha_{B-1})\\ (\beta_2)(\alpha_{B-1})\\ \vdots \\ (\beta_{C-1})(\alpha_{B-1})\\ \end{bmatrix} $
$\Sigma \alpha = \sum\limits_{i=1}^{B-1} \alpha_i \quad : \alpha_i \in \mathbb{R}[0, 1] $
$\Sigma \beta = \sum\limits_{j=1}^{C-1} \beta_j \quad : \beta_j \in \mathbb{R}[0, 1] $
With the target coordinate known as well as all the boundary coordinates, this system of equations can be solved to obtain the boundary weights $\beta$. This however cannot be done with linear algebra seeing that this is a non-linear expression.
If any $\alpha_i$ < 0, $\alpha_i$ > 1 or $\beta_j$ < 0, $\beta_j$ > 1 the target coordinate is outside the boundaries and tie-simplices connecting the sets of boundary coordinates.