This question is obviously related to Are Voronoi diagrams used in kNN algo implementations?, but I'd like to ask a couple more question than there.
I am considering using Voronoi diagram to speed up kNN in a situation where the number of training points is much smaller than the number of test points, on the order of 100 and 1000000 respectively, with only 2 features, so it may make sense to build the Voronoi diagram for the training set if it's going to speed up inference for the test points.
1) Are Voronoi diagrams usable, regardless of performance, for $k>1$? They are obviously directly usable for $k=1$, but I don't see immediately how to apply them for larger $k$.
2) For $k=1$ and with training data of size $m$ is it possible to find from the Voronoi diagram the nearest neighbor faster than $O(m)$? For a giving test point one can find all distances to the training points in $O(m)$, so Voronoi diagram may be useful only if it can help find the nearest neighbor faster than $O(m)$.