Introduction

Following up with my last post on NCH being roto-translation invariant, the idea of this one is to cover what I consider the most important gaps left by the original brief paper. My expectation is that doing this will help understand better why NCH works, and hopefully gain some insight into how to improve it.

Equivalence of formulations

Equation (4) in the paper says:

$$f_i^{r_i} (x) = \frac{1}{2 r_i} (r_i^2 - || x - (p_i + r_i n_i) ||^2)$$

However, the definition used in (2) is slightly different. Where does (2) come from? from expanding inner products in the second term of the sum:

\begin{align} || x - (p_i + r_i n_i) ||^2 & = \langle x - p_i - r_i n_i, x - p_i - r_i n_i \rangle \\
& = \langle x - p_i, x - p_i \rangle + \langle x - p_i, -r_i n_i \rangle + \langle -r_i n_i, x - p_i \rangle + \langle -r_i n_i, -r_i n_i \rangle \\
& = || x - p_i ||^2 + (-2 r_i) \langle n_i, x - p_i \rangle + r_i^2 \end{align}

Thus, when you replace in the original definition:

\begin{align} f_i^{r_i} (x) & = \frac{1}{2 r_i} (r_i^2 - (|| x - p_i ||^2 + (-2 r_i) \langle n_i, x - p_i \rangle + r_i^2)) \\
& = \frac{1}{2 r_i} (- || x - p_i ||^2 + (2 r_i) \langle n_i, x - p_i \rangle) \\
& = \langle n_i, x - p_i \rangle - \frac{1}{2 r_i} || x - p_i ||^2 \end{align}

Which is exactly what we wanted

Fantastic $\rho_i$s and where to find them

In equation (3), the author says what the value of $\rho_i$ should be. He later defines $r_i$ as the largest value of $r$ such that $f_i^r (p_j) \leq 0 \forall p_j \in \mathcal{P}, j \neq i$. If you actually write it out:

$$ 0 \geq f_i^r (p_j) = \langle n_i, p_j - p_i \rangle - \frac{1}{2 r_i} || p_j - p_i ||^2 $$

And thus

$$ \frac{1}{2 r_i} \geq \frac{ \langle n_i, p_j - p_i \rangle }{ || p_j - p_i ||^2 } $$

If you gather the contraints for all $p_j$s together, then you have that

$$ \rho_i \geq \max_{p_j \in \mathcal{P}, i \neq j} \frac{ \langle n_i, p_j - p_i \rangle }{ || p_j - p_i ||^2 } $$

And we further need that $\rho_i \geq 0$ in the case the supporting set actually ends up being just the linear half space (as should happen when fitting planes, for example).

$\rho$s and $\theta$s

One interesting thing to notice out of the estimation of $\rho$ is that (in non-standard notation, but good enough for understanding):

\begin{align} \rho_i & = \max_{p_j \in \mathcal{P}, i \neq j} \{ 0, \frac{\langle n_i, p_j - p_i \rangle}{|| p_j - p_i ||^2} \} \\
& = \max_{p_j \in \mathcal{P}, i \neq j} \{ 0, \frac{1}{|| p_j - p_i ||} \langle n_i, \frac{p_j - p_i}{|| p_j - p_i ||} \rangle \} \\
& = \max_{p_j \in \mathcal{P}, i \neq j} \{ 0, \frac{\text{cos_sim} (n_i, p_j - p_i)}{|| p_j - p_i ||} \} \\
\end{align}

Where $\text{cos_sim}$ denotes the cosine similarity between the two vectors; i.e. the angle between them. For the following plots, I have set $p_i = (1, 1)$ and $n_i = (1, 0)$, and plotted the component in the maximum above for the given points (notice $p_i$ is NOT included in the plot, for obvious reasons), as well as the cosine similarity:

Results are as you would expect: towards the outside of the surface (i.e. in the inverse direction as the normal) we get negative values, and towards the inside we get positive. However, contribution of a point to the maximum decreases really fast as you move away from the center point, because the cosine similarity is bounded between $-1$ and $1$, while the distance it is divided by can be arbitrarily large.

This may be an interesting way to construct an heuristic to speed up NCH: process only the $O(\sqrt N)$ points that are closest when computing the rho.