Sorting Pairs of Points Based on Their Distances

Abstract

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.

Authors and Affiliations

Mohammad Farshi, Abolfazl Poureidi, Zorieh Soltani

Keywords

Related Articles

A Review of Embedding Hexagonal Cells in the Circular and Hexagonal Region of Interest

Hexagonal cells are applied in various fields of research. They exhibit many advantages, and one of the most important is their possibility to be closely packed and to form a hexagonal grid that fully covers the Region o...

The Dynamics of IT Workaround Practices - A Theoretical Concept and an Empirical Assessment

An interesting phenomenon that has received limited attention in the extant literature is that of IT workaround practices. Based on Ashby's Law of Requisite Variety, workarounds were found to be used to accomplish the ba...

Improved Hybrid Model in Vehicular Clouds based on Data Types (IHVCDT)

In Vehicular Cloud (VC), vehicles collect data from the surrounding environment and exchange this data among the vehicles and the cloud centers. To do that in an efficient way first we need to organize the vehicles into...

Status of Wireless Technologies Used For Designing Home Automation System - A Review

The concept of “Automation” have just started flourishing, companies have developed automated systems of their own to control alarms, sensors, actuators and video cameras and moving further the concept of automated build...

Fast Approximation for Toeplitz, Tridiagonal, Symmetric and Positive Definite Linear Systems that Grow Over Time

Linear systems with tridiagonal structures are very common in problems related not only to engineering, but chemistry, biomedical or finance, for example, real time cubic B-Spline interpolation of ND-images, real time pr...

Download PDF file
  • EP ID EP159286
  • DOI 10.14569/IJACSA.2016.070278
  • Views 94
  • Downloads 0

How To Cite

Mohammad Farshi, Abolfazl Poureidi, Zorieh Soltani (2016). Sorting Pairs of Points Based on Their Distances. International Journal of Advanced Computer Science & Applications, 7(2), 626-630. https://europub.co.uk/articles/-A-159286