Rapid K-Neighbor Identification Algorithm for the Sphere
Author: Hodgson, Michael E.
Source: Cartography and Geographic Information Science, 1 July 1992, vol. 19, no. 3, pp. 165-174(10)
Abstract: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.
Document Type: Research Article
Publication date: July 1, 1992