If I'm given the distances of some point $p$ from $n$ coplanar points, can I tell whether $p$ is also coplanar?

Question

I've been thinking for some time about this problem, however I'm not yet sure how to approach it.
There are a few ways to think about this, however I'll give it exactly as in the original applied problem I'm trying to solve. Consider a network of $n$ coplanar nodes in $2$-dimensions, with known coordinates, and a signal with velocity $v$, with arbitrary coordinates $(x,y)$ and emitted at an unknown time $t$.
I've written an algorithm which is able to reconstruct the coordinates of the signal source $(x,y)$ given only the signal velocity $v$ and the time of arrival at each node, assuming the source is also coplanar with the nodes.
The Problem:
Given the time at which the signal reached each node (or, if you like, all $frac{n(n-1)}{2}$ time of arrival differences), how can we determine whether it may correspond to a source coplanar with the nodes (a source in $2$-dimensions). Or, if you like, how can we flag input as "invalid" before passing it to the algorithm?
My Thinking:
I know that the minimum possible time of arrival difference can be found by computing the centroid of the $n$ nodes, and taking a signal source at that location, then computing the time of arrival for each node from this point. I also know that the maximum possible time of arrival difference will be for the two furthest nodes (the "diameter" of the set, if you like, or the diameter of the minimum bounding sphere).
Will restricting input to lying between this minimum and maximum be sufficient enough to exclude input that corresponds to sources outside of the plane formed by the nodes?
There will be $infty$ possible source locations in $2$-dimensions, but (I think) an even larger $infty$ of locations in $3$-dimensions.

I could also phrase this as "given the distance of some point $p$ from $n$ coplanar points, how can I determine whether $p$ is also coplanar with the $n$ points by examining the distances?

I'm interested not only in solving this as an applied problem, but also understanding the deeper meaning that must exist behind this. How can I look at $n$ times of arrival, and tell whether it definitely corresponds to a source in $3$-dimensions? Or, at least, something close to this.
EDIT: this looks like it may be useful, though I don't quite follow yet (and it seems a bit overkill).

Y Tong · Answer

As this is probably coming from a set of noisy data, a least-squares algorithm might work better. I would go with $p=arg! min_{tilde{p}inmathbb{R}^3} sum_{ineq j} (|tilde{p}-p_i|-|tilde{p}-p_j|-(t_i-t_j))^2$,  and then check if $p$ is in the plane containing $p_i$'s, assuming that you have a large enough number of known points.
If there are few points, then for each pair of points, you actually know that the source point cannot be far from the hyperboloid determined by the difference in time of arrival. The intersections of these hyperboloids should have a point close to the plane.

KeithMadison · Answer

This is a start, and I'm very open to alternative answers & modifications

According to:
If $A$, $B$, $C$, and $D$ are four points in a plane, then the Cayley-Menger determinant vanishes. That is,
$$detbegin{pmatrix}
0 & 1 & 1 & 1 & 1\
1 & 0 & |AB|^2 & |AC|^2 & |AD|^2\
1 & |AB|^2 & 0 & |BC|^2 & |BD|^2\
1 & |AD|^2 & |BD|^2 & |CD|^2 & 0
end{pmatrix} =0$$
As @leo pointed out, I'm not sure if the implication goes both ways (although it seems reasonable)

If I'm given the distances of some point $p$ from $n$ coplanar points, can I tell whether $p$ is also coplanar?

2 Answers

Add your own answers!

Ask a Question