Exercise 6.8

Here is how we implement $F(S,x)$:

(a)

Set the nearest neighbor be $x_{\mathit{nn}}=\text{None}$ as in python.

(b)

If the input cluster has no children cluster, i.e. it has at most 2 data points

• Find the nearest neighbor in the cluster by computing the distance from $x$ to all the points in the cluster. There are at most 2 computations needed since we assume every cluster with more than 2 points is split into 2 sub-clusters.
• Return this point as the nearest neighbor $x_{\mathit{nn}}$ in the input cluster to $x$
• Else, suppose the two children clusters of input cluster are: $S_1,S_2$
• If $\parallel x-{\mu }_1\parallel \le \parallel x-{\mu }_2\parallel$: let $x_{\mathit{nn}}=F(S_1,x)$
• Else: let $x_{\mathit{nn}}=F(S_2,x)$

(c)

Now we have $x_{\mathit{nn}}$, let’s call the sibling cluster of $S$ be $S^{\text{∗}}$, let’s compute the bound condition

(d)

If $\parallel x-x_{\mathit{nn}}\parallel >\parallel x-{\mu }^{\text{∗}}\parallel -r^{\text{∗}}$: (Need check cluster $S^{\text{∗}}$ for the nearest neighbor)

• $x_{\mathit{nn}}^{\text{∗}}=F(S^{\text{∗}},x)$
• If $\parallel x-x_{\mathit{nn}}^{\text{∗}}\parallel <\parallel x-x_{\mathit{nn}}\parallel$: $x_{\mathit{nn}}=x_{\mathit{nn}}^{\text{∗}}$

(e)

Return $x_{\mathit{nn}}$