You are given a set of n points in the 2D plane. Each point p_i is given by its

Question

You are given a set of n points in the 2D plane. Each point p_i is given by its x and y coordinates (x_i, y_i). Two points are called identical if one is obtained from the other by multiplication by the same number (scalar multiplication). So for example (10, 15), (2, 3) and (100, 150) are identical, but (10, 15) and (10, 20) are not. (a) Suggest an algorithm that runs in worst case time O(n log n) and determines whether the input contains two identical points. That is, whether among the n points, you could find a pair which is identical. (b) Repeat, but now the expected running time is O(n).

Explanation / Answer

(a) To find pair of identical points among n points, we could iterate over all the points and find out. What we can do is for two sets of points (x1,y1) and (x2,y2) we can check they are identical if x1*y2 - x2*y1 is equal to zero.
Let's say we have (10,15), (2,3), (100,150) and (10,20) as set of n points. So, for (10,15) we have to compare it with n-1 values, and similary, total number of comparisons would be 3 + 2 + 1 = 6 which is nearly equal to 4*log4.

(b) To obtain the same result in O(n) time complexity, we can use hashing. First of all reduce all the points to their ratio i.e. (10,15) is reduced to 0.66667. And then store it in hash table, this would take O(n) time. At the time of insertion just check if there is same value existing i.e. (2,3) is represented as 0.66667, so we check and we find that (10,15) is also the same. Hence, there is a match. Searching in hash table takes O(1) time, so in total O(n) + O(1) = O(n).

I hope this clarifies your doubt, feel free to comment if you still have any questions.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.