In my current problem, I am looking for an algorithm to reconstruct the position of multiple points in the 2D euclidean plane with incomplete distance information, $d_{ij}=||x_j-x_i||\in\text{dom}_a$. E.g. Information is:

  • $x_i$: $\{d_{ii},d_{ij}, d_{ik}, d_{il}\}\in \text{dom}_a$
  • $x_j$: $\{d_{ji}, d_{jj}, d_{jk}\} \in \text{dom}_a$, $\{d_{jl}\} \in \text{dom}_b$
  • there are more than 2 domains and all domains are non overlapping.

This "binned distance" information is exact and is available of all points. I like to find the positions or rather areas with high likelihood, where the points can be found.

Currently I think, I have too less information to solve the nonlinear constrained optimization problem. On the other hand, I believe it should be enough to make a Bayesian approach work.

Information, I also have but currently don't make use of:

  • the binned distance information are from time series and $\max(dx/dt)$ is known. This might be useful for finding the next solution of a given configuration in time.

Any suggestions how to obtain these regions of possible positions are appreciated.

Edit Example of forward Problem

To answer the questions I added a picture of the forward problem. Black dots represents all positions I like to reconstruct. For two points (green and blue) I exemplary plotted their bins (circle) for which I get the information.

E.g. For the two points close to the blue center, blue would return: $d_{\text{blue},1}$ and $d_{\text{blue},2}$ are within bin 2 where as $d_{\text{green},1}$ reports within bin 5 and $d_{\text{green},2}$ within bin 6. I do have the radius information for each bin.

All bins are a subset of the real line. Their union represents the real line. Their intersection is empty.

  • $\begingroup$ I don't understand your notation. What is $\text{dom}_a$ supposed to be? A set of possibly distances? And are you suggesting that some of the distances between points are in some subset of distances, and other distances in other subsets? Are these domains intervals of the real line, or discrete? $\endgroup$ Dec 3, 2016 at 1:37
  • $\begingroup$ And do you actually know the exact distances, or do you only know which bin it is in? $\endgroup$ Dec 3, 2016 at 1:37
  • $\begingroup$ @WolfgangBangerth I added a picture which illustrates the problem. I know exactly which bin it is in and I also now the size of each bin. $\endgroup$
    – Bort
    Dec 5, 2016 at 11:58


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.