1
$\begingroup$

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 is
i) Inefficient brute-force and
ii) 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.

$\endgroup$
  • $\begingroup$ I suggest you start thinking about the corresponding problem with three points. Here are some suggestions: (i) try using Lagrange multipliers to find the feasible solution (one zeroing the determinant) which is closest to the given data in some metric of your choice, (2) use known methods in numerical optimization such as gradient descent. $\endgroup$ – Yuval Filmus Nov 5 '14 at 2:45

Your Answer

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

Browse other questions tagged or ask your own question.