2
$\begingroup$

Hi,

Is there a way to find a function $F : \mathbb S^2 \rightarrow \mathbb R^3$ of class $\mathcal C^1$, minimizing $$\int_{\mathbb S^2\times\mathbb S^2} (d(F(x),F(y)) - \delta(x,y))^2 ~dx ~dy$$ , where $d$ stands for the euclidean distance in $\mathbb R^3$ and $\delta$ the geodesic distance on the sphere $\mathbb S^2$?

I tried to perform a Multi-Dimensional Scaling to get this least square solution for a finite set of point, but it seems that the solution was just the identity... is that right?

Thanks!

Improve this question
$\endgroup$
21
  • $\begingroup$ I have no clue what the OP is asking for. Voting to close unless clarified. $\endgroup$
    – Igor Rivin
    Commented Jun 7, 2011 at 14:48
  • $\begingroup$ I did my best to rewrite the question and clarify. Thanks for the feedbacks. $\endgroup$
    – WhitAngl
    Commented Jun 7, 2011 at 15:05
  • $\begingroup$ Let me understand if I understood correctly. You have $n$ points $p_1, \cdots , p_n$ on the standard unit sphere $\mathbb{S}^2$ in $\mathbb{R}^3$. You're asking about the existence of points $q_1, \cdots , q_n$ on $\mathbb{S}^2$ such that $d(q_i,q_j)=\delta (p_i,p_j)$, where $d$ is the Euclidean distance and $\delta$ is the geodesic distance w.r.t. the spherical metric? $\endgroup$
    – Qfwfq
    Commented Jun 7, 2011 at 15:14
  • $\begingroup$ yes - up to the fact that an approximation is fine if an exact solution cannot be found ; and that the $q_i$ could be anywhere in $R^3$, not necessarily on $S^2$ $\endgroup$
    – WhitAngl
    Commented Jun 7, 2011 at 15:18
  • $\begingroup$ (continued) ...and you want the assignement $p_i \mapsto q_i$ to be realized by the same function $F=(f,g,h):\mathbb{S}^2\to\mathbb{S}^2$. Which regularity are you assuming about $F$ ? Does it have to extend to a function (with the same regularity) $\mathbb{R}^3\to\mathbb{R}^3$ ? $\endgroup$
    – Qfwfq
    Commented Jun 7, 2011 at 15:20

2 Answers 2

Reset to default
3
$\begingroup$

Although I cannot answer your question precisely, I thought I would suggest a possible direction to pursue: embeddings of finite metric spaces with low distortion. With those keywords you will hit a rich literature. Perhaps the place to start is this Handbook article by Piotr Indyk and Jiri Matousek:

"Low distortion embeddings of finite metric spaces," Handbook of Discrete and Computational Geometry, 177-196, CRC, 2004. (Google books link)

For example, Bourgain's embedding theorem say that any $n$-point metric space can be embedded in $\ell_2$ with $O( \log n )$ distortion (where distortion is defined by a factor times the source distance $\delta(x,y)$ bounding the target distance—not quite your least squares, but a reasonable measure). Unfortunately this embedding might be into a rather high dimension, which is not what you want. Matousek proved that there are $n$-point metric spaces that require distortion $\Omega(n^{1/2})$ for embedding into $\ell^3_2$ (i.e., $\mathbb{R^3}$), which does not bode well for your problem.

Unfortunately, negative results abound. Here is one, not directly relevant (because both spaces have $n$ points), but its more recent references may help:

"Hardness of Embedding Metric Spaces of Equal Size," Subhash Khot and Rishi Saket, Proceedings of the 10th International Workshop on Approximation, 2007.

To skirt these negative results, you might have to somehow exploit the fact that your source distances are geodesics on a sphere.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not familiar with the term "n-point metric" : does it mean that we consider a discrete space consisting of only n points ? In this case, the result can be directly obtained constructively using methods such as MDS, IsoMap, LLE, eigenmaps ..., isn't it ? Or is it different ? $\endgroup$
    – WhitAngl
    Commented Jun 8, 2011 at 23:39
  • $\begingroup$ Yes, $n$ points with distances forming a metric space, as satisfied by $n$ points on a sphere. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 9, 2011 at 0:02
1
$\begingroup$

Let's say that the sphere is with the center at $(0,0,0)$ and has the radius $1$. Let's take the points $p_1=(0,0,1)$, $p_2=(0,0,-1)$, $p_3=(1,0,0)$, $p_4=(0,1,0)$. The distances are $\delta(p_1,p_3)=\delta(p_1,p_4)=\delta(p_3,p_4)=\delta(p_2,p_3)=\delta(p_2,p_4)=\pi/2$, and $=\delta(p_1,p_2)=\pi$. Now let's try to find in $\mathbb R^3$ four points $q_i$ at the same distances. $q_1,q_3,q_4$ and $q_2,q_3,q_4$ are equilateral triangles, with the length of the edges equal to $\pi_2$. The distance $d(q_1,q_2)\leq \pi\sqrt 3/2$. But we need to have $d(q_1,q_2)=\pi$, and this cannot happen.

Edit: It seems that the question has changed. I'll let this counterexample anyway.

Improve this answer
$\endgroup$
1
  • $\begingroup$ ok, thanks, this already tells me that an exact solution cannot be found. Do you know about a least-square solution ? Thanks! $\endgroup$
    – WhitAngl
    Commented Jun 7, 2011 at 16:25

You must log in to answer this question.

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