0

I have a smooth $n-1$-surface embedded in $R^n$. I have a way to find a point on the surface along a given line, and a way to compute the tangent plane at a given point on the surface. I would like to find the orthogonal projection of an arbitrary point $x$ onto the surface. My current thought is to do something not unlike Newton's method:

  1. find an arbitrary point on the surface $y$
  2. compute the tangent plane at $y$
  3. find the point on the surface $y'$ along the line passing through $x$ and normal to the tangent plane in step 2.
  4. $y \leftarrow y'$
  5. GOTO 2

I have concerns about step 3 simply failing because there is no intersection between the surface and the computed line. I also am not confident that this algorithm will converge. Is there a better way to go about this problem? Are there any relevant extensions of Newton's method that may give me some convergence guarantees under suitable conditions?

Him
  • 447
  • 1
    What do you mean by a point orthogonal to another point> – Rushabh Mehta Nov 26 '19 at 17:43
  • Do you understand that for many cases there is no such a point? That can be one of the reasons, why your step 3 is failing sometimes. – Vasily Mitch Nov 26 '19 at 17:44
  • @DonThousand the orthogonal projection. I have updated the question. – Him Nov 26 '19 at 17:45
  • @Scott As Vasily notes, there is no guarantee such a point exists, so there is no general method. So no, there's no extension that will guarantee convergence. – Rushabh Mehta Nov 26 '19 at 17:47
  • @VasilyMitch do you have any simple examples? I am having a hard time imagining such a thing. – Him Nov 26 '19 at 17:47
  • I can imagine a scenario where the projection is not unique. A counterexample where there is no such point would be interesting. – Him Nov 26 '19 at 17:51
  • Ok, I was wrong. I haven't read it carefully and jumped to conclusions. I will write an answer to you. – Vasily Mitch Nov 26 '19 at 17:59

1 Answers1

1

Your steps 3-4 should be:

3) take a small step from point $y$ along the tangent plane in the direction of $x$: $z=y+\varepsilon t$

4) get point $y'$ on the surface that lies on the line $(x,z)$

Modification of step 4 includes: if angle between tangent plane in $y'$ and line $y'-x$ becomes smaller, go back to step 3 and decrease the step size $\varepsilon$.

Vasily Mitch
  • 10,129
  • To paraphrase: "Move along a line given by a vector very close to the previous line, but moved a little bit toward the normal vector for the tangent plane from step 2". Is this correct? If so, this seems reasonable. I'm not crazy about having to hand-tune the (starting) $\epsilon$ parameter, but such is life, I suppose. – Him Nov 26 '19 at 18:19
  • 1
    Yes, you can move either along the tangent line or line (y,x) itself. In most optimization problems (and this problem is equivalent to one) where we use gradient decent, tuning the learning rate $\varepsilon$ is something that cannot be avoided. – Vasily Mitch Nov 26 '19 at 18:26