If you have any additional references which you would like added, please let us know at challenge6@dimacs.rutgers.edu.

Bibliography

AM92

Pankaj Agarwal and Jirí Matousek.
Ray shooting and parametric search.
In Proc. 24th ACM Symp. Theory Comp., pages 517-526, 1992.

AMN+94

Sunil Arya, David Mount, Nathan Netanyahu, Ruth Silverman, and Angela Wu.
An optimal algorithm for approximate nearest neighbor searching.
In Proc. 5th ACM Symp. on Discrete Algorithms, pages 573-583, 1994.

Ben75

Jon L. Bentley.
Multidimensional binary search trees used for associative searching.
Communication of the ACM, 18(9):509-517, 1975.

Bri95

Sergey Brin.
Near neighbor search in large metric spaces.
In Proc. 21st Inter. Conf. on Very Large Data Bases, pages 574-584, 1995.

Cla88

Kenneth Clarkson.
A randomized algorithm for closest-point queries.
SIAM J. Comput., 17(4):830-847, 1988.

Cla94

Kenneth Clarkson.
An algorithm for approximate closest-point queries.
In Proc. 10th ACM Symp. on Computational Geometry, pages 160-164, 1994.

Cla97

Kenneth Clarkson.
Nearest neighbor queries in metric spaces.
In Proc. 39th ACM Symp. Theory Comp., pages 609-617, 1997.

DL76

David Dobkin and Richard Lipton.
Multidimensional searching problems.
SIAM J. Comput., 5(2):181-186, 1976.

FS82

C. Feustel and L. Shapiro.
The nearest neighbor problem in an abstract metric space.
Pattern Recognition Letters, 1:125-128, 1982.

IMRV97

Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh Vempala.
Locality-preserving hashing in multidimensional spaces.
In Proc. 39th ACM Symp. Theory Comp., pages 618-625, 1997.

Kle97

Jon Kleinberg.
Two algorithms for nearest-neighbor search in high dimensions.
In Proc. 39th ACM Symp. Theory Comp., pages 599-608, 1997.

Mat91

Jirí Matousek.
Reporting points in halfspaces.
In Proc. 32nd Symp. on Found. Comput. Sci., pages 207-215, 1991.

Mei93

Stefan Meiser.
Point location in arrangements of hyperplanes.
Information and Computation, 106(2):286-303, 1993.

MS97

Nimrod Megiddo and Uri Shaft.
Efficient nearest neighbor indexing based on a collection of space filling curves.
Technical Report IBM Research Report RJ 10093 (91909), IBM Almaden Research Center, San Jose California, 1997.

Mul91

Ketan Mulmuley.
Randomized multidimensional search trees: Further results in dynamic sampling (extended abstract).
In Proc. 32nd Symp. on Found. Comput. Sci., pages 216-227, 1991.

Sam89

Hanan Samet.
The Design and Analysis of Spatial Data Structures.
Addison-Wesley, Reading, Ma, 1989.

Uhl91

Jeffrey K. Uhlmann.
Satisfying general proximity/similarity queries with metric trees.
Information Processing Letters, 40(4):175-179, 1991.

Yia93

Peter Yianilos.
Data structures and algorithms for nearest neighbor search in general metric spaces.
In Proc. 4th ACM Symp. on Discrete Algorithms, pages 311-321, 1993.

YY85

Andrew Yao and Frances Yao.
A general approach to d-dimensional geometric queries.
In Proc. 17th ACM Symp. Theory Comput., pages 163-168, 1985.

Previous DIMACS Implementation Challenges.

DIMACS Home Page.