Sorting Pairs of Points Based on Their Distances
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2016, Vol 7, Issue 2
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
- EP ID EP159286
- DOI 10.14569/IJACSA.2016.070278
- Views 93
- Downloads 0
Case-Based Reasoning for Selecting Study Program in Senior High School
One of the reasoning methods in expert system is Case-Based Reasoning (CBR). A problem is searching for past cases in the case base with thehighest similarity degree. This implies that calculation of similarity degree am...
Validation Policy Statement on the Digital Evidence Storage using First Applicable Algorithm
Digital Evidence Storage is placed to store digital evidence files. Digital evidence is very vulnerable to damage. Therefore, making digital evidence storage need access control. Access control has several models, one o...
A Survey on Attacks and Defense Metrics of Routing Mechanism in Mobile Ad hoc Networks
A Mobile Ad hoc Network (MANET) is a dynamic wireless network that can be formed infrastructure less connections in which each node can act as a router. The nodes in MANET themselves are responsible for dynamically disco...
Detection of Distributed Denial of Service Attacks Using Artificial Neural Networks
Distributed Denial of Services (DDoS) is a ruthless attack that targets a node or a medium with its false packets to decline the network performance and its resources. Neural networks is a powerful tool to defend a netwo...
Causal Impact Analysis on Android Market
Google play store contains a large repository of apps for android users. Play store has two billion active users that have two million apps to download and use. App developers are competing to get a higher success rate a...