# Estimating distance between two points in n-dimensional space, with knowledge of other paths

Suppose there exist four randomly distributed points in $n$-dimensional space: $A$, $B$, $C$, and $D$.

We have no knowledge of the coordinates of any of these points, but we do know nearly all of the distances:

$\overline{AB} = j_1$

$\overline{BD} = j_2$

$\overline{AC} = j_3$

$\overline{CD} = j_4$

We have, in other words, the distances from $A$ to $D$ via each of the other points, but not the distance $\overline{AD}$ itself (nor the distance $\overline{BC}$ between these intermediary points).

Clearly, we can't determine the precise distance $\overline{AD}$, though we can be sure that it's less than the smaller of $j_1 + j_2$ and $j_3 + j_4$.

My question is this: is there any way to go about formulating an estimate for $\overline{AD}$? How would this estimate change if we were to have more or fewer intermediary points?

• You also know that $\overline{AD}\ge\lvert j_1-j_2\rvert$ and $\overline{AD}\ge\lvert j_3-j_4\rvert$. The more intermediate points, the greater the number of intervals within which you know $\overline{AD}$ must lie. Unless you know something about the distribution of the intermediate points, I don’t think you can determine whether any value in the intersection of these intervals is more or less likely than any other. – Steve Kass Dec 25 '14 at 5:37
• Surely the optimal estimate depends on the random distribution used. – Travis Willse Dec 25 '14 at 5:42
• @SteveKass Well-taken! Suppose, however, that we were to have not one but two intermediary points, thereby creating three distances ($k_1$, $k_2$, and $k_3$, let's say, instead of $j_1$ and $j_2$). The upper bound would follow the same pattern ($k_1 + k_2 + k_3$), but is there a way of determining the lower bound without brute forcing every combination of addition and subtraction? – Hank Dec 25 '14 at 19:05
• At first thought, I don’t think so. Imagine three lengths of macaroni strung together between two knots with just enough play to allow folding. It’s easy to see how far apart you can get the end knots from each other: just unfold the thing into a straight line. But if you want to know how close you can get the end knots to each other, I don’t see how you can find out without trying at least some of the various ways of folding the thing up. There might be some efficiencies (maybe the two longest lengths should go in opposite directions?). – Steve Kass Dec 25 '14 at 19:28
• @SteveKass Great analogy. The brute-forcing would scale as $O(2^n)$, but since the operation is simple addition and subtraction it wouldn't be prohibitive for small sets of intermediate points. – Hank Dec 25 '14 at 20:01