Consider four points$i,j,k,l$and their pairwise Euclidiean distances$d(ij)$$d(ik)$$d(il)$$d(jk)$$d(jl)$$d(kl)$  Say that, we know the coordinates of the points $j$, $k$ and $l$.However, we do not know where $i$ is and the measured distances to $i$ are erroneous depending on an error rate $e\%$.That means, given the distance $d(ij)$, the actual distance is between $d(ij)*(1-e)$ and $d(ij)*(1+e)$.Given the fact that those 4 points are coplanar, which means Cayley-Menger determinant (CMD) of the distances is zero, I seek an efficient way to find the values for $d(ij)$, $d(ik)$, $d(il)$.So far, I have thought about dividing the distance interval into $k$ and trying all the possible combinations, which gives me $O(k^3)$ complexity.for(ij=ijMin; ij<=ijMax; ij+=(ijMax-ijMin)/10)    for(ik=ikMin; ik<=ikMax; ik+=(ikMax-ikMin)/10)        for(il=ilMin; il<=ilMax; il+=(ilMax-ilMin)/10)            if(CMD(ij, ik, il, jk, jl, kl) == 0)                return {ij, ik, il};However, this method isi) Inefficient brute-force andii) Does not guarantee to return a solution.If you propose an algorithm that is efficient is OK for me. I do not seek for an exact solution. But also I do not want to spend $O(k^3)$ time.
Modifying the Erroneous Pairwise Distances of 4 Points to Get Coplanarity
algorithms;computational geometry;euclidean distance