0
$\begingroup$

Suppose we have two points $p_1$ and $p_2$ in a metric space with unknown dimensionality, with no way to directly compute the distance between them, e.g. no coordinates.

Say we can randomly sample a set of points $P$ in this space. And say we can calculate the distance between any pair of points in $P$, the distance between any point in $P$ and $p_1$, and the distance between any point in $P$ and $p_2$.

The question I have is: can the distance between $p_1$ and $p_2$ be estimated using points in $P$ and the distances we can calculate with them? Is there some triangulation scheme that would work, without knowing dimensionality? Even if the distance cannot be calculated with certainty is there some statistical estimate? Relatedly, are there restrictions we can place on the space that make this problem tractable?

An observation is that the distances between a point in $P$ and points $p_1$ and $p_2$ is a lower bound on the distance between $p_1$ and $p_2$. But this seems like a very weak bound.

Any guidance or feedback would be deeply appreciated. Thank you very much.

Improve this question
$\endgroup$
5
  • $\begingroup$ It might be helpful to be more specific about the setup, because answer might depend on details. Plus it's not clear in which situation distances between p_i and points in P should be computable while distance between p_1 and p_2 isn't $\endgroup$
    – alesia
    Commented Aug 3, 2022 at 15:52
  • $\begingroup$ was thinking about this as a survey -type problem. for example, there are two satellites, and we want to know the distance between them using distance measurements between the satellite and known ground locations. so I think there are concrete examples of this kind of set up. thanks very much for your help. $\endgroup$
    – CambridgeStudent
    Commented Aug 3, 2022 at 15:55
  • $\begingroup$ a key distinction between the satellite example and the setup of the question, is we don't know the dimensionality of the space. so a simple solution of intersecting three spheres would not work in general. $\endgroup$
    – CambridgeStudent
    Commented Aug 3, 2022 at 16:02
  • 1
    $\begingroup$ ok I see. I think the current formulation is lacking too many details for a mathematical treatment. In your three satellite example, there's clearly no way of finding the distance you want $\endgroup$
    – alesia
    Commented Aug 3, 2022 at 17:03
  • $\begingroup$ I believe distance can be determined in the satellite example, if dimension is known $\endgroup$
    – CambridgeStudent
    Commented Aug 3, 2022 at 17:27

1 Answer 1

Reset to default
4
$\begingroup$

It seems to me that in the general setting of a metric space, what one learns from the sampling data will be precisely the bounds provided by the instances of the triangle inequality that must be obeyed.

That is, for any sampled point $p$, the distance $d(p_1,p_2)$ must obey:

  • $d(p_1,p_2)\leq d(p_1,p)+d(p,p_2)$,
  • $d(p_1,p)\leq d(p_1,p_2)+d(p_2,p)$, and
  • $d(p_2,p)\leq d(p_1,p_2)+d(p_1,p)$.

In other words, the unknown distance is bounded above and below like this: $$|d(p_1,p)-d(p_2,p)|\quad\leq \quad d(p_1,p_2)\quad \leq \quad d(p_1,p)+d(p,p_2).$$

This is all and only the information that is provided, because any number between these bounds is possible in some metric space, simply because the metric space consisting of the sampled points and the two target points will itself be a metric space, provided that the distance obeys those triangle inequalities, since those are the only remaining instances of the triangle inequality to be checked.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .