Far point queries in high dimensions
See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web...

http://dblp.org/rec/conf/soda/GoelIV01


Yep, here is a postscript of the full version:

http://web.stanford.edu/~ashishg/papers/reductions.ps

(Postscript is a file format used in the 20th century to ensure that future generations would not be able to read the content of the file.)