Keep Your Friends Close and Your Enemies Closer: The Art of Proximity Searching
David M. Mount · 2006
Proximity searching is the general term used for various distance-based search problems in geometric and metric space settings. It includes the well known nearest neighbor problem and its relatives, such as range searching, distance selection, and point location. In spite of many years of research, this field remains a fruitful source of new ideas, new problems, and new computational challenges. It is also one of the success stories of algorithm design, where theory has informed the design of the latest software innovations, and algorithm experimentation has led to new theoretical insights. In this talk, we will survey some recent results in this area and present directions for future research and challenges.