Suppose that we have a plane $P$ whose equatoin is unknown.

However, we know some pairwise Euclidean distances $|p_1q_1|, \dots, |p_nq_n|$ between some points $p_1, \dots, p_n$ on P to some other points $q_1, \dots, q_n$ on $z=0$ plane.
Moreover, we know all the pairwise distances in the set $p_1, \dots, p_n$ (we can assign relative coordinates to them in $2D$.

For which value of $n$ can we find the equation of $P$?

I approach this problem as follows.

  1. Draw $n$ spheres $S_1, \dots, S_n$ where each $S_i$ is centered at $q_i$, and its radius is $|p_iq_i|$.
  2. Take two arbitrary spheres $S_i$ and $S_j$ with radii $r_i, r_j$ respectively.
  3. Find all the point pairs $(a,b)$ such that $a \in S_i,\ b \in S_j$ and $|ab| = |p_ip_j|$ (remember that we know all pairwise distances between $p_i,p_j|\ i,j \in \{1,\dots,n\}$.
  4. We obtain a (possibly non linear) equation $f(n)$.
  5. Now, take another sphere $S_k$ and repeat steps 2 and 3 for $S_i, S_k$ and $S_j, S_k$

After step 5, I am stuck. I cannot tell if the solution space expands or not, and if there is an lower bound for $n$ that allows us to solve the above problem.

  • $\begingroup$ @amd This comment really helps me. But out of curiosity, how did you guess that I will work with noise in the future? :) $\endgroup$ – padawan Sep 6 '17 at 23:35
  • $\begingroup$ There’s always some sort of error due to noise and other causes in real-world data. Theoretically-correct solution sometimes fail miserably as a result. $\endgroup$ – amd Sep 7 '17 at 5:41
  • $\begingroup$ @amd I think the plane is not necessarily a tangent to the spheres. It can also intersect them. $\endgroup$ – padawan Sep 7 '17 at 15:27
  • $\begingroup$ You’re right. I was thinking of a different situation. $\endgroup$ – amd Sep 7 '17 at 17:53

I don’t believe that this process will converge in general. Suppose, for instance, that $|p_iq_i|=1$ for all $i$. Any plane parallel to the $z=0$ plane and within a distance of $1$ from it satisfies these point-pair distance constraints, and many others do as well. I suspect that the best that you’re going to be able to do with this pair distance data is to limit the possibilities somewhat.

For each of the points $q_i=(x_i,y_i,0)$, the plane must intersect the sphere with radius $r_i=|p_iq_i|$ centered at $q_i$. Working in homogeneous coordinates, this sphere can be represented by the matrix $$S=\begin{bmatrix}1&0&0&-x_i\\0&1&0&-y_i\\0&0&1&0\\-x_i&-y_i&0&x_i^2+y_i^2-r_i^2\end{bmatrix}.$$ If we represent the plane by the vector $(\lambda,\mu,\nu,\tau)^T$, then this intersection condition can be stated as $$P^TS^{-1}P\le0.$$ Using the adjugate $S^{\tiny\triangle}$ instead of $S^{-1}$ might be more convenient since it eliminates division by $r^2$. The matrix $S^{\tiny\triangle}$ represents a quadric surface (the dual to the constraining sphere, in fact), so the constraint can be interpreted as requiring the vector that represents the plane to lie within a region bounded by this quadric surface, and thus the solution space consists of the intersection of these regions. The solution space certainly gets no larger with each additional point-distance pair, but there’s no particular reason that I can see to expect that the intersection will consist of a single point, either.

  • $\begingroup$ Thank you! And thank you again. This is a very nice explaination that pushes research further. $\endgroup$ – padawan Sep 7 '17 at 20:13

Your Answer

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

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