For those interested in this space, folks might like some of the work that went in to visualizing T Distributed Stochastic Neighbor Embedding and the successor to that LargeVis which use multiple forms of KNN trees each with their own trade offs:

https://arxiv.org/abs/1301.3342 (Barnes Hut)

https://arxiv.org/abs/1602.00370 (LargeVis)

One uses Vantage Point Trees which sudivides the space in to quadrants, and the other uses Random Projection Trees.

Both are interesting exercises in using KNN like techniques to visualize high dimensional spaces.