Abstract: Finding out the closest pair of points has been widely applied in many areas,such as the geographic information query system and spatial databases etc．But so far,there is not an efficient algorithm for the problem．For example,the divide and conquer algorithm contains much comparison,slow convergence and much computing of the distance between two points．Grid-based methods used to solve the nearest neighbor problem can not determine the size of the grid reasonably,and they are inefficient．For this reason,a single-direction detecting algorithm (CP_SDD) was presented in the paper．Then a row-divided sorting algorithm was proposed．Finally,an algorithm based on row-divided sorting and single-direction detecting for finding the closest pair of points (CP_SDD+RDS) was formed．Compared with the divide and conquer algorithm,our algorithm not only efficiently overcomes these drawbacks that occur in the divide and conquer algorithm,the row-divided strategy of the RDS algorithm is also effective to solve these problems that occur in grid-based methods．A large number of experiments show that the CP_SDD+RDS algorithm is efficient and feasible.

Key words: Closest pair of points,Right-angled distance,Fuzzy distance,Point density,Point-intensive areas