and a query point , find the closest point in to . Donald Knuth in volume 3 of The Art of Computer Programming (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a -NN search, where we need to find the closest points.

Most commonly is a metric space and dissimilarity is expressed