Nearest point on Spherical Cap

Question

Let $A \subset \mathbb{S}^n$ be a spherical cap. More specifically, there exists a point $v \in \mathbb{S}^n$ and $\epsilon > 0$ such that $A = \{u \in \mathbb{S}^{n}\mid v\cdot u \geq \epsilon\}$.

Given some point $w \in \mathbb{S}^n$, I would like to find point in $A$ which minimizes the distance to $w$. If $w$ is not $A$, such a point would need to lie on the boundary of $A$.

I've tried solving this analytically, but it results in quite an ugly formula. I'm wondering if there's any known closed form solution to the problem.

Thanks.

Answer 1

I'll try to answer my self.

For a point $w \in \mathbb{S}^{n}$ denote by $u$ the the vector orthonormal to $v$ which lies on the great circle connecting $w$ to $v$. Explictly, $u' = w - (w,v)v$ and $u = \frac{u'}{|u'|}$.

Now, on one hand, the point closest to $w$ in $A$ must lie on the boundary of A. On the other hand it lies on the arc connecting $v$ to $u$. So, it will suffice to find the intersection of the boundary and the arc.

The boundary of $A$ is precisely those points whose inner product with $v$ equals $\epsilon$. And we can parametrize the arc between $w$ and $u$ to be $cos(t)u + sin(t)v, t \in [0, \frac{\pi}{2}]$.

Solving the equation yields: $(cos(t)u + sin(t)v,v) = \epsilon \implies sin(t) = \epsilon$. And we have $t = arcsin(\epsilon)$. This gives the closest point to be $cos(arcsin(\epsilon))u +\epsilon v$. Alternatively $(\sqrt{1-\epsilon^{2}})u + \epsilon v$.

Note, ofcourse this is only true when the cap does not contain an entire hemisphere ($\epsilon > 0$) otherwise it's not even a geodesic convex set and the closest point is not even well defined.

Answer 2

What you are looking for is the solution to this convex optimization problem: $$\begin{array}{ll} \text{minimize} & \tfrac{1}{2}(u-w)^T(u-w) \\ \text{subject to} & \tfrac{1}{2} u^Tu \leq \tfrac{1}{2} \\ & v^T u \leq \epsilon \end{array}$$ The $\tfrac{1}{2}$ coefficients are just for convenience below. We can find a solution using a Lagrangian approach. The Lagrangian is $$L(u,\lambda_1,\lambda_2) = \tfrac{1}{2}(u-w)^T(u-w) - \lambda_1\tfrac{1}{2}(1-u^Tu) - \lambda_2(\epsilon - v^T u)$$ where $\lambda_1,\lambda_2\geq 0$. The optimality conditions are $$u-w+\lambda_1 u+\lambda_2 v = 0 \quad u^Tu \leq 1 \quad v^T u \leq \epsilon \quad \lambda_1,\lambda_2 \geq 0$$ and then the complementary slackness conditions: $$\lambda_1(1-u^Tu)=0 \quad\Longrightarrow\quad \lambda_1=0 ~\text{or}~ u^Tu = 1$$ $$\lambda_2(\epsilon -v^Tu)=0 \quad\Longrightarrow\quad \lambda_2=0~\text{or}~v^Tu=\epsilon$$ The equality condition can be written as follows: $$(1+\lambda_1) u = w - \lambda_2 v \quad\Longrightarrow\quad u = (1+\lambda_1)^{-1} ( w - \lambda_2 v ).$$ So here's what this tells us. To find $u$, we move along the line $w - \lambda_2 v$ by adjusting $\lambda_2$. Eventually, we will hit the plane $v^Tu=\epsilon$, but this might put us outside of the sphere; i.e., $u^Tu>1$. If that happens, we need to scale the point $u$ so that $u^Tu=1$. But doing that messes up $v^Tu=\epsilon$, so we have to tweak again...

If you want, you can work a bit to express this more mathematically. But assuming that $w^Tw\le 1$ and $v^Tw<\epsilon$, I'm confident enough you can proceed as follows:

1. First, determine $\lambda_2\geq 0$ such that $v^T(w-\lambda_2v)=\epsilon$.
2. If this $u=w-\lambda_2v$ satisfies $u^Tu\leq 1$, STOP, that's your answer (and $\lambda_1=0$).
3. Otherwise, you need to solve for $\lambda_1$, $\lambda_2$ in this pair of equations: $$\frac{1}{(1+\lambda_1)^2}(w-\lambda_2 v)^T(w-\lambda_2 v) = 1 \quad \frac{1}{1+\lambda_1} v^T(w-\lambda_2 v) = \epsilon$$

It looks like you can express $\lambda_1$ in terms of $\lambda_2$ rather easily using the second equation; then, substituting this into the first equation, you'll get a polynomial in $\lambda_2$. Find the most sensible root, and you're done.

Note that the KKT optimality conditions do not assume that $w$ is in the sphere or outside of the cap. So it is possible to come up with an algorithm here that works for any $w$. For instance, if $w$ is already inside the cap, the conditions immediately imply that $u=w$ and $\lambda_1=\lambda_2=0$.