0
$\begingroup$

Let's assume that the points $\in \mathbb{R}^2$ and there are only C=5 points (in practice, I may have $\mathbb{R}^{800}$ and 1000 points). The first out of the five points is fixed. We also have been given a vector $v$ which has distances between all possible pairs made from the C=5 points (thus $C*(C-1)=10$ in this case).

The problem is to create a configuration out of $(C-1)$ points ($C-1$ points since the first point is always fixed) that obeys the distances given in $v$. Let's denote the set points as $X \in \mathbb{R}^{D \times C}$.

My approach:

I thought this should be a solvable problem since we have the freedom of moving $C-1$ points anyway we want. So I turned to optimization-based approach. Remember that $x_1$ is always fixed.

$$ minimize \sum_{i=2}^C \sum_{j=i-1}^C ||x_i-x_j||_2^2 \\ subject \ to: ||x_2-x_1||_2^2 > v_1 \\ ||x_3-x_1||_2^2 > v_2 \\ \vdots \\ ||x_C-x_1||_2^2 > v_C \\ ||x_3-x_2||_2^2 > v_{C+1} \\ \vdots \\ ||x_C-x_2||_2^2 > v_m \\ \vdots \\ ||x_C-x_{C-1}||_2^2 > v_n \\ $$

I have put the constraints to obtain the distances between points as per given in $v$. Note that the constraints are only "greater than", so as a counter-effect and to control the distances between the points, I minimize the objective function.

My results

I use fmincon of MATLAB for this. It works in the sense that it does obey all the constraints but puts all the points a little far away than desired (i.e. more farther than mentioned in $v$).

First of all, I am an amateur in optimization and geometry. I am not too sure whether this has a feasible solution (i.e. it assigns the distances in v within a very small margin). So if a slight change in the objective function and the constraints will make this work, I am open to that too.

$\endgroup$
  • 1
    $\begingroup$ This is a classical problem known as multidimensional scaling. The least-squares solution can be obtained directly by linear algebra, see e.g. the notes by Wickelmaier in sec. 2.1 under "Steps of a classical MDS algorithm". $\endgroup$ – Rahul Jan 31 '16 at 19:51
  • $\begingroup$ Thanks! How did I miss MDS! $\endgroup$ – Parag S. Chandakkar Jan 31 '16 at 20:06

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.