Geometric Algorithms for $k$-NN Poisoning

We propose a label poisoning attack on geometric data sets against $k$-nearest neighbor classification. We provide an algorithm that can compute an $\epsilon n$-additive approximation of the optimal poisoning in $n\cdot 2^{2^{O(d+k\mathrm{/}\epsilon )}}$ time for a given data set $X\in {\mathbb{R}}^d$, where $\mathrm{\mid }X\mathrm{\mid }=n$. Our algorithm achieves its objectives through the application of multi-scale random partitions.