A New Improved Algrithom of Two-Dimensional Closest Point Pair
Jun Ma, Bangcheng Zhan, Feng Li · 2019
The problem of two-dimensional closest point pair is the basic problem in the process of geometry research and computer development. And other areas such as aviation also involve it. For this problem, this paper first introduces the current research status, and then proposes an improved algorithm with lower time complexity based on the classical algorithm (making the time complexity of the algorithm reduce to 4/3nlgn). Moreover, a new point pair detection theorem is proposed, which can determine the number of detection points according to the region, making the algorithm more efficient.