This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now.
Here, I summarize the original problem:
- We have points in 3D space.
- We do not know the coordinates of the points.
- We know some of the pairwise Euclidean distances.
- Those points are deployed on random planes.
- We neither know the number nor the equations of the planes.
Problem is to find an algorithm that extracts the coplanar point groups.
Now, I struggle with a slightly changed version of the problem.
Suppose that, distance measurements are not precise. We have a variable, called error rate, which tells us the possible deviation of a distance measurement.
For example: The Euclidean distance between any arbitrary point pair is $d = 10$ and the error rate is $e = 1\%$.
When we give the graph as input, that particulat distance $d$ may range from $9.9$ to $10.1$.
If $e$ is $5%$, then $d \in [9.5, 10.5]$ etc.
Now, we have another challenge, which is, even though 4 points are on the same plane, Cayley-Menger determinant may result a negative number, because of the violation of the triangle inequality.
Can we extract the planes even though the distances are erroneous?
Please notice that, the coordinates of the points are not known. However, if it makes any difference, you may assume that the coordinates of a number of arbitrary points are known.