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.

So far, this and this answers helped me to approach the original problem.

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.

  • $\begingroup$ You want to detect groups of 4 points that are co-planar, but what does it mean for 4 points to be co-planar, in this setting? Does it mean that there is a way to move each point slightly so that they are co-planar and so that the Euclidean distances are within 1% of the measured values? Note that there might be false alarms: i.e., 4 points which actually aren't co-planar, but because they are close to co-planar, are treated as co-planar by this definition. Is this OK? $\endgroup$
    – D.W.
    Commented Oct 24, 2014 at 3:39
  • $\begingroup$ @D.W. 4 points are not necessarily coplanar but accepted as coplanar because the volume of the tetrahedron they formed is less than the tolerance value. $\endgroup$
    – padawan
    Commented Oct 25, 2014 at 21:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.