Find center of N concentric spheres given N radii and N points on respective spheres

61 Views Asked by At

Given $N$ points $\{(x_i, y_i, z_i)\}_{i=1}^N$ that lie on $N$ concentric spheres each with a respective radius $R_i,$ what is their common center $(\bar{x},\bar{y},\bar{z})?$

Of course since there are three unknowns this should be uniquely solvable when $N = 3$ (maybe?). For en exact solution you have a system a $N$ equations:

$$ (x_i - \bar{x})^2 + (y_i - \bar{y})^2 + (y_i - \bar{y})^2 = R_i^2,\ \ \ i=1\ldots N $$

Numerically this can be treated as a minimization problem:

$$ \mbox{argmin}_{(\bar{x},\bar{y},\bar{z})} \sum_{i=1}^N \left[ (x_i - \bar{x})^2 + (y_i - \bar{y})^2 + (y_i - \bar{y})^2 - R_i^2\right]^2 $$

and we can use some method like Gradient Descent. I was wondering if there is a more direct way to solve this problem? I also need to know if there is no solution. Any good approaches?

EDIT: Following up on @john-omielan's solution we have the linear system $A\bar{c} = b:$

$$ \left[\begin{array}{lll} \Delta x_1 & \Delta y_1 & \Delta z_1 \\ \Delta x_2 & \Delta y_2 & \Delta z_2 \\ \vdots & \vdots & \vdots \\ \Delta x_{N-1} & \Delta y_{N-1} & \Delta z_{N-1} \end{array}\right] \left[\begin{array}{c} \bar{x} \\ \bar{y} \\ \bar{z} \end{array}\right] = -\frac{1}{2} \left[\begin{array}{c} \Delta R_1^2 - (\Delta x_1^2 + \Delta y_1^2 + \Delta z_1^2) \\ \Delta R_2^2 - (\Delta x_2^2 + \Delta y_2^2 + \Delta z_2^2) \\ \vdots \\ \Delta R_{N-1}^2 - (\Delta x_{N-1}^2 + \Delta y_{N-1}^2 + \Delta z_{N-1}^2) \end{array}\right] $$

where $\Delta x_1 = x_{i+1} - x_i,$ $\Delta x^2_i = x^2_{i+1} - x^2_i,$ (likewise for $y$ and $z$) and $\Delta R_i^2 = R_{i+1}^2 - R_i^2.$ When $N = 4$ then $A$ is a $3 \times 3$ matrix which, if not singular, yields a unique solution. If $N > 4$ then we have an over-constrained solution so we solve

$$ A^T A \bar{c}^* = A^T b $$

which yields a least-squares solution $\bar{c}^*.$

C++ code snipper for solution here.

1

There are 1 best solutions below

1
On BEST ANSWER

As you stated, you have

$$(x_i - \bar{x})^2 + (y_i - \bar{y})^2 + (z_i - \bar{z})^2 = R_i^2 \tag{1}\label{eq1}$$

The $x_i, y_i, z_i, R_i$ are known, with the $\bar{x}, \bar{y}, \bar{z}$ being the unknowns. In general, if you $n \ge 4$, you can determine whether or not there is a unique solution and, if there is, what that is. As amd suggested in a comment, you can try to find the intersection of the spheres to solve a possibly over-constrained set of equations. This is because expanding \eqref{eq1} gives you

$$\left(x_i^2 - 2x_i\bar{x} + \bar{x}^2\right) + \left(y_i^2 - 2y_i\bar{y} + \bar{y}^2\right) + \left(z_i^2 - 2z_i\bar{z} + \bar{z}^2\right) = R_i^2 \tag{2}\label{eq2}$$

For $1 \le i \le n - 1$, if you use \eqref{eq2} with index $i$ and subtract from it \eqref{eq2} but using index $i+1$, you get

\begin{align} \left(x_i^2 - x_{i+1}^2\right) - 2(x_i - x_{i+1})\bar{x} + \left(y_i^2 - y_{i+1}^2\right) - 2(y_i - y_{i+1})\bar{y} \\ + \left(z_i^2 - z_{i+1}^2\right) - 2(z_i - z_{i+1})\bar{z} = R_i^2 - R_{i+1}^2 \tag{3}\label{eq3} \end{align}

Since the square terms of the bar variables have canceled, you're left with a linear equation in $3$ unknowns of $\bar{x}, \bar{y}, \bar{z}$. Note if you later use any second index instead of $i + 1$, you'll get a linear combination of the ones already calculated (e.g., \eqref{eq1} with $i = 1$ minus \eqref{eq1} with $i = 3$ is the same as adding the first $2$ equations determined earlier for $i = 1$ and $i = 2$). Thus, you have $n - 1$ linear equations in $3$ unknowns, so $n = 4$ is the minimum needed to possibly get a unique answer.

Note that some of these equations may still be linearly dependent on other ones or are inconsistent with each other. Also, with $n \gt 4$, you'll get an over-constrained system. If there is not a unique solution with these systems of equations, then you know you don't have a solution. Also, even if you determine a solution, you may still find it's inconsistent with \eqref{eq1} for at least some $1 \le i \le n$, so you also won't have a unique solution then either. In these cases, you may wish to determine a closest solution as a minimization problem you suggest, or perhaps use some method to get a best fit result using these system of linear equations.