When, if ever, is nearest neighbor classification the best choice?
One situation where NN would be ideal is if the data are sample points of a piecewise constant function. In this case, the true function is composed of a tesselation of its domain, with a constant value for all points within each division.