Introduction and Orientation by Vladlen

• The closest-point algorithm is also described in Kleinberg-Tardos, Section 13.7.
• The k-Enclosing Minimum Disk algorithm is also described in Vladlen's notes, Section 5.2.2.

Har-Peled notes, Section 2

• Quadtrees are also briefly described in Vladlen's notes, Sections 5.2.1 and 5.2.2.

Fill in details, background, and related work from:

• Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu: An Optimal Algorithm for Approximate Nearest Neighbor Searching. J. ACM 45(6): 891-923 (1998)
• Kenneth L. Clarkson: An Algorithm for Approximate Closest-Point Queries. Symposium on Computational Geometry 1994: 160-164
• Timothy M. Chan: Approximate Nearest Neighbor Queries Revisited. Discrete & Computational Geometry 20(3): 359-373 (1998)

Fill in details, background, and related work from:

• Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998: 604-613
• Sariel Har-Peled: A Replacement for Voronoi Diagrams of Near Linear Size. FOCS 2001: 94-103
• S. Sen, N. Sharma, Y. Sabharwal: Nearest Neighbors Search using Point Location in Balls with applications to approximate Voronoi Decompositions. Journal of Computer and System Sciences, Volume 72(6) , September 2006, Pages 955-977.

Fill in details, background, and related work from:

• Sariel Har-Peled: A Replacement for Voronoi Diagrams of Near Linear Size. FOCS 2001: 94-103
• Sunil Arya, Theocharis Malamatos: Linear-size approximate Voronoi diagrams. SODA 2002: 147-155
• Sunil Arya, Theocharis Malamatos, David M. Mount: Space-efficient approximate Voronoi diagrams. STOC 2002: 721-730
• S. Sen, N. Sharma, Y. Sabharwal: Nearest Neighbors Search using Point Location in Balls with applications to approximate Voronoi Decompositions. Journal of Computer and System Sciences, Volume 72(6) , September 2006, Pages 955-977.

Fill in details, background, and related work from:

• Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998: 604-613
• Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. SIAM J. Comput. 30(2): 457-474 (2000)
• Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni: Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. Symposium on Computational Geometry 2004: 253-262
• Alexandr Andoni, Mayur Datar, Nicole Immorlica, Vahab S. Mirrokni, P. Indyk: Locality-sensitive hashing using stable distributions, in Nearest Neighbor Methods in Learning and Vision: Theory and Practice, T. Darrell, P. Indyk, G. Shakhnarovich (eds.), MIT Press, 2006.

• Piotr Indyk: Dimensionality Reduction Techniques for Proximity Problems. SODA 2000: 371-378.
• Ashish Goel, Piotr Indyk, Kasturi R. Varadarajan: Reductions Among High Dimensional Proximity Problems. SODA 2001: 769-778

• Kenneth L. Clarkson: Nearest Neighbor Queries in Metric Spaces. Discrete & Computational Geometry 22(1): 63-93 (1999)
• Kenneth L. Clarkson: Nearest-neighbor searching and metric space dimensions, in Nearest Neighbor Methods in Learning and Vision: Theory and Practice, T. Darrell, P. Indyk, G. Shakhnarovich (eds.), MIT Press, 2006.

• Amit Singh, Hakan Ferhatosmanoglu, Ali Saman Tosun: High Dimensional Reverse Nearest Neighbor Queries. CIKM '03.
• F. Korn, S. Muthukrishnan: Influence sets based on reverse nearest neighbor queries. SIGMOD '00.