Rapid K-Neighbor Identification Algorithm for the Sphere
Michael Edward Hodgson · Cartography and Geographic Information Systems · 1992
Spatial searching, such as the identification of k-nearest neighbors to a point, is one of the most time-intensive tasks in vector-based geographic information systems transformational or analytical operations, and as such continues to impede many studies. While a number of computationally efficient k-neighbor searching algorithms have been developed for d-dimensional monotonic coordinate axes, these methods are inappropriate for spherical coordinates necessary in many global studies. This article briefly examines the assumptions and resulting limitations of k-neighbor searching algorithms with spherical coordinates. One of the simplest, yet most efficient k-neighbor searching algorithms is applicable to spherical applications, if constrained. Comparisons between the processing efficiency of the brute-force searching method commonly in use, a constrained heuristic k-neighbor searching algorithm, and a modified k-neighbor algorithm indicate processing times may be decreased by as much as 99% using such rapid searching methods in global geographic applications.