Proximity and Monotone Matrix Search Algorithms

Algorithms that answer search queries over data with a geometric or ordered structure, using that structure to avoid examining every item. Nearest neighbor search finds the point in a set that is closest or most similar to a query point under a distance or dissimilarity function, and the SMAWK algorithm finds the smallest value in each row of an implicitly defined totally monotone matrix and is named after the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber and Maria Klawe. An algorithm belongs here when its cited article describes proximity search or the search of a monotone matrix. It excludes plain scans of a list, which sit with the sequential search algorithms, and searches of a sorted list by key.