About a density property of the Nearest Neighbor algorithm Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and $(\mathcal{X},d)$ be metric space. Suppose that $X,X_1,X_2,X_3,... : \Omega\to\mathcal{X}$ are $\mathbb{P}$-i.i.d. random variables.
Get a closed set $K$ of $(\mathcal{X},d)$ and $x\in\partial K$.
Suppose that:
$$\exists r_x>0, \exists \delta_x >0, \forall r\in(0,r_x), \frac{\mathbb{P}(X\in K\cap B_r (x))}{\mathbb{P}(X\in B_r (x))}\ge \delta_x+\frac{\mathbb{P}(X\in K^c\cap B_r (x))}{{\mathbb{P}(X\in B_r (x))}},$$
where $B_r(x)$ is the open ball centered in $x$ of radius $r$ in $(\mathcal{X},d)$.
Define: $$\forall m\in\mathbb{N}, \pi_m^x: \mathcal{X}^m\to\{1,...,m\}, (x_1,...,x_m)\mapsto \min\left(\operatorname{argmin}_{k\in\{1,...,m\}}\left(d\left(x,x_1\right),...,d\left(x,x_m\right)\right)\right).$$
Define:
$$\forall m\in\mathbb{N}, Z_m^x:\Omega\to\mathcal{X}, \omega\mapsto X_{\pi_m^x\left((x,X_1(\omega),...,X_m(\omega)\right)}(\omega).$$

Is it true that $\mathbb{P}(Z_m^x\in K^c)\to 0, m\to\infty?$

Intuitively, since if $m$ is big enough we have that $\mathbb{P}(Z_m^x\in K^c\cap B_{r_x}(x))$ is close to $\mathbb{P}(Z_m^x\in K^c)$, the dynamic is definitively governed by what happens in $B_{r_x}(x)$ and inside this ball is more likely to get $X\in K$ instead of $X\in K^c$... however, I didn't find a way to convert this intuition into a proof.
 A: Possible counter-example
I am not 100% sure of some claims below (and also not sure I interpret your question correctly), so apologies if this doesn't work...  Critiques most welcome!
Each of the i.i.d. $X$'s is generated by this process:


*

*First generate an underlying $Y \sim Uniform(0,1)$ (i.i.d.)

*Now do a $Bernoulli(p = \frac23)$ trial and if success (i.e. with prob $\frac23$) we assign $X=Y$ but if failure (i.e. with prob $\frac13$) then assign $X=-Y$.

*So the pdf $f$ of $X$ has support $(-1, 1)$ and is piecewise-constant with $f(x) = \frac13$ for $x\in (-1, 0)$ and $f(x) = \frac23$ for $x\in (0, 1)$.
Now take $x=0$ and $K=[0,1]$.  Then $P(X \in K \mid X \in B_r(x)) = \frac23$ for any $r \in (0,1)$, so the pre-condition is satisfied with $\delta = \frac13$.
However, what is $P(Z_m \in K^c)$?
$Z_m$ is the $X_i$ that is closest to $x=0$, and among all the $X_i$, the one closest to $x=0$ is the one with the minimum underlying $Y_i$.  By construction, there is $\frac13$ chance this $Y_i$ turned into a negative $X_i$, which would be $\in K^c$.  Thus, I think $P(Z_m \in K^c) = \frac13$ for any $m$, and the limit is also $\frac13$.
Again: I'm not 100% sure of all the arguments nor of the interpretation of your question.  Critiques welcome!
