Embedding a set of $n$ points with a given metric in $\mathbb{R}^n$.

Hopefully someone can help me with a reference for this problem, or the construction. I have a metric defined on $n$ points in $\mathbb{R}^2$. Is it possible to find a higher dimensional Euclidean space so that you can place $n$ points in such a way that these distances are attained with the standard metric? If it is possible, is there a formula of some sort to determine the locations (up to rigid motions)?

To make it more explicit:
If $\{x_i\}$ are the original points with distances $d(x_i, x_j)$ and $\{y_i\}$ are the images in $\mathbb{R}^N$, find $y_i$ such that
$$|y_i – y_j| = d(x_i, x_j)$$

Solutions Collecting From Web of "Embedding a set of $n$ points with a given metric in $\mathbb{R}^n$."

This is not always possible. Let $e_1=(1,0)$ and $e_2=(0,1)$ be the standard basis vectors in $\mathbb R^2$. Take $X=\{e_1,e_2,-e_1,-e_2\}\subseteq\mathbb R^2$, equipped with the $\infty$-metric, i.e. $$d(e_1,e_2)=d(e_1,-e_2)=d(e_2,-e_1)=d(-e_1,-e_2)=1$$ and $$d(e_1,-e_1)=d(e_2,-e_2)=2.$$

This space $X$ cannot be isometrically embedded into any $\mathbb R^n$. The reason is as follows: suppose $f:X\to\mathbb R^n$ is an isometric embedding. Since $$2=d(e_1,-e_1)=d(e_1,e_2)+d(e_2,-e_1)=1+1,$$ we must have $$\|f(e_1)-f(-e_1)\|=\|f(e_1)-f(e_2)\|+\|f(e_2)-f(-e_1)\|.$$ But in the euclidean case, equality in the triangle inequality is possible only if the points are collinear. In fact, comparing the distances, $f(e_2)$ has to be the midpoint between the other two: $$f(e_2)=\frac{f(e_1)+f(-e_1)}2.$$ Similarly, $$2=d(e_1,-e_1)=d(e_1,-e_2)+d(-e_2,-e_1)=1+1,$$ so we must have $$f(-e_2)=\frac{f(e_1)+f(-e_1)}2.$$ But this means that $f(e_2)=f(-e_2)$, contradicting the fact that $f$ is an embedding.