AN IMPROVED ALGORITHM ABOUT THE CLOSEST PAIR OF POINTS ON PLANE SET

In the paper the divide and conquer algorithm about the closest pair of points on plane set is improved, which was pressented by Preparata and Shamos in 1985. Their algorithm needs at most 3 n calculations on distance, and the time complexity is 3 n log n in worst case. The improved algorithm only needs at most 2 n calculations on distance, and the time complexity of calculation on distance is reduced to 2 n log n .