Existance and uniqueness of solution for a point with fixed distances to three other points

116 Views Asked by At

I have two sets of known points in $\mathbb{R}^2$: Four points $\mathbf{p_1}, \mathbf{p_2}, \mathbf{p_3}, \mathbf{p_x}$ , and three other points $\mathbf{q_1}, \mathbf{q_2}, \mathbf{q_3}$. I would like to find $\mathbf{q_x}$ such that the ratios of Euclidian distances between $\mathbf{q_x}$ and $\mathbf{q_1}, \mathbf{q_2}, \mathbf{q_3}$, are the same as between $\mathbf{p_x}$ and $\mathbf{p_1}, \mathbf{p_2}, \mathbf{p_3}$. That is, I want to find $\mathbf{q_x}$ such that

$\frac{d(\mathbf{q_1},\mathbf{q_x})}{\sum_i d(\mathbf{q_i},\mathbf{q_x})} = \frac{d(\mathbf{p_1},\mathbf{p_x})}{\sum_i d(\mathbf{p_i},\mathbf{p_x})}$ and $\frac{d(\mathbf{q_2},\mathbf{q_x})}{\sum_i d(\mathbf{q_i},\mathbf{q_x})} = \frac{d(\mathbf{p_2},\mathbf{p_x})}{\sum_i d(\mathbf{p_i},\mathbf{p_x})}$ and $\frac{d(\mathbf{q_3},\mathbf{q_x})}{\sum_i d(\mathbf{q_i},\mathbf{q_x})} = \frac{d(\mathbf{p_3},\mathbf{p_x})}{\sum_i d(\mathbf{p_i},\mathbf{p_x})},$

where $d(\cdot,\cdot)$ is the Euclidian distance. Or to rewrite it a bit nicer:

$d(\mathbf{q_x},\mathbf{q_k}) = w \cdot d(\mathbf{p_x},\mathbf{q_k}) $ for $ k = 1,2,3$,

where $w$ is the unknown factor $w = \frac{\sum_i d(\mathbf{q_i},\mathbf{q_x})}{\sum_i d(\mathbf{p_i},\mathbf{p_x})}$. Note also the more to the point problem formulation by Blue in the comments.

This looks like three equations with three unknowns (x-, and y- coordinates of $\mathbf{q_x}$ and $w$). However, I have been struggling for quite a while now to find out if there is always a unique solution, and to find this solution, or to find an optimal solution if no solution exists.

Any help that you can offer is greatly appreciated!

1

There are 1 best solutions below

1
On BEST ANSWER

I'll work from the re-formulation I gave in a comment, but with a minor notational changes.


Given non-negative $u$, $v$, $w$ such that $u+v+w=1$, and given a non-degenerate $\triangle ABC$, we seek a point $P$ such that $$\frac{|PA|}{u} = \frac{|PB|}{v} = \frac{|PC|}{w} = |PA|+|PB|+|PC| =: r \qquad (1)$$

For convenience, introduce these coordinates: $$A = (0,0) \qquad B = (c, 0) \qquad C = ( b \cos A, b \sin A ) \qquad P=(x,y)$$

where $b$, $c$ (and, below, $a$) are lengths of the sides opposite angles $B$, $C$ (and $A$) in $\triangle ABC$. Then, from $(1)$, write

$$\begin{align} (x-0)^2 + ( y - 0 )^2 = r^2 u^2 \quad &\to \quad x^2 + y^2 = r^2 u^2 \\ (x-c)^2 + ( y - 0 )^2 = r^2 v^2 \quad &\to \quad x^2+y^2-2xc + c^2 = r^2 v^2 \\ (x-b \cos A)^2 + ( y - b \sin A )^2 = r^2 w^2 \quad &\to \quad x^2+y^2-2xb\cos A - 2 y b \sin A+ b^2 = r^2 w^2 \\ \end{align}$$

We can use the first equation to eliminate $x^2+y^2$ from the other two equations. (In effect, we're determining the radical axis of each pair of circles.) The result is a linear system $$\begin{align} 2 x c &= c^2 + r^2 \left( u^2 - v^2 \right) \\ 2 x b \cos A + 2 y b \sin A &= b^2 + r^2 \left( u^2 - w^2 \right) \end{align}$$

whose solution is (after some manipulation that probably needs to be double-checked) $$\begin{align} x &= \frac{1}{2c}\left( c^2 + r^2 \left( u^2 - v^2 \right) \right) \\ y &= \frac{1}{2bc\sin A}\left( a b c \cos C + r^2 \left( u^2 a \cos B + v^2 b \cos A - w^2 c \right) \right) \end{align}$$

Substituting these coordinates into the first circle equation gives a quadratic equation in $r^2$:

$$\begin{align} 0 &= r^4 \; \left( \; a^2 ( v^2 - u^2 ) ( u^2 - w^2 ) + b^2 ( w^2 - v^2 ) ( v^2 - u^2 ) + c^2 ( u^2 - w^2 ) ( w^2 - v^2 ) \; \right) \\ &+ 2 r^2 a b c \; \left( \; u^2 a \cos A + v^2 b \cos B + w^2 c \cos C \; \right) \\ &- a^2 b^2 c^2 \end{align}$$

If the coefficient of $r^4$ vanishes ---for instance, when (and only when?) $u=v=w$--- we have $$r^2 = \frac{a b c}{2\; \left( \; u^2 a \cos A + v^2 b \cos B + w^2 c \cos C \; \right)} \qquad (2) $$

Otherwise, we invoke the Quadratic Formula, noting that the discriminant factors nicely as $$\begin{align} &\phantom{\cdot} \left(a+b+c\right)\left(-a+b+c\right)\left(a-b+c\right)\left(a+b-c\right) \\ &\cdot\left(ua+vb+wc\right)\left(-ua+vb+wc\right)\left(ua-vb+wc\right)\left(ua+vb-wc\right) \end{align}$$

The first set of factors constitute Heron's Formula for $16T^2$, where $T$ is the area of $\triangle ABC$. The second set of factors can be interpreted as $16{T_\star}^2$, where $T_\star$ is the area of an auxiliary triangle whose sides are $ua$, $vb$, $wc$ (if such a triangle exists!). We conclude that $$r^2 = \frac{\pm 8 T T_\star - a b c \; \left( \; u^2 a \cos A + v^2 b \cos B + w^2 c \cos C \; \right)}{a^2 ( v^2 - u^2 ) ( u^2 - w^2 ) + b^2 ( w^2 - v^2 ) ( v^2 - u^2 ) + c^2 ( u^2 - w^2 ) ( w^2 - v^2 )} \qquad (3)$$

With an appropriate choice for "$\pm$", we can substitute-back into the formulas for $x$ and $y$ to find $P$. That messy business is left as an exercise for the reader.


I'm not prepared to assert that $u=v=w$ is the only circumstance under which the coefficient of $r^4$ vanishes, putting equation $(2)$ into play. Nevertheless, note that when the coefficient doesn't vanish, solution to the problem requires that $$\left(ua+vb+wc\right)\left(-ua+vb+wc\right)\left(ua-vb+wc\right)\left(ua+vb-wc\right) \ge 0$$

(so that $r^2$ is real). This equation is equivalent the the existence of the auxiliary triangle with sides $ua$, $vb$, $wc$, which is therefore necessary for the existence of $P$. Confirmation (or refutation) that it is also sufficient is another exercise for the reader.


As for uniqueness of the solution (when it exists): The independence of the linear system would seem to guarantee that.