Sorting Pairs of Points Based on Their Distances

Sorting data is one of the main problems in computer science which studied vastly and used in several places. In several geometric problems, like problems on point sets or lines in the plane or Euclidean space with higher dimensions, the problem of sorting pairs of points based on the distance (between them is used. Using general sorting algorithms, sorting n 2) distances between n points can be done in O(n2 log n) time. Ofcourse, sorting (n2) independent numbers does not have a faster solution, but since we have dependency between numbers in this case, finding a faster algorithm or showing that the problem in this case has O(n2 log n) time complexity is interesting. In this paper, we try to answer this question.

@article{Farshi2016,
  title     = {Sorting Pairs of Points Based on Their Distances},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {7},
  number    = {2},
  year      = {2016},
  publisher = {The Science and Information Organization},
  author    = {Mohammad Farshi and Abolfazl Poureidi and Zorieh Soltani},
  doi       = {10.14569/IJACSA.2016.070278},
  url       = {https://doi.org/10.14569/IJACSA.2016.070278}
}