0

Given n points in the plane. Let's say that a point at coordinate (x1,y1) dominates another point (x2,y2) if x1 ≤ x2 and y1 ≤ y2.

We try, for each point p, to compute the number of points that p dominated them. How we can use Divide and conquer approach to this problem to solve it in O(n log n)?

I think as follow, we sort points by x coordinate then according to the middle point, we split points into two sections, now at this step, I get stuck.

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
ErroR
  • 131
  • 5
  • 1
    This forum is for programming problems. Please add some code and post your errors. For algorithmic questions you can ask in other forums. Good luck. – Reza Akraminejad May 01 '22 at 12:04
  • Additionally, I can't remember the name of this problem, but it is fairly common. You can find multiple references for this if you look it up – Abhinav Mathur May 01 '22 at 14:10
  • dominating points? I check that and this problem is very close to it, but we try to count for each point, a number of points that a point dominates them. – ErroR May 01 '22 at 14:14
  • 1
    Does this answer your question? [A divide-and-conquer algorithm for counting dominating points?](https://stackoverflow.com/questions/19510564/a-divide-and-conquer-algorithm-for-counting-dominating-points) – Def Soudani May 01 '22 at 14:26

1 Answers1

0

Sort the given points using any nlogn sorting algo(quick sort or merge-sort). where the comparison function takes both x and y into account. Now, since we have sorted list/array, we can do a binary search on this sorted array to find the position of the input point. Now, we have the position in sorted array, all the points below this position is what we needed. If you are using array as your data-structure , due to one-off nature, the position is your answer.

Time complexity:- Sorting takes n * log n Binary search takes log n Returning the position is 0(1).

Total = n * log n + log n + 1

When compared to n * logn, (log n + 1) is just a constant and this constant becomes relatively very small for a very large data-set. So, your overall complexity is still n * log n.

For example let us say the number of data point is 100. Then, 100 * log (100) = 200. (Taking base as 10). log(100) + (100 * log(100)) = 202.

You see, the additional log(n) makes the time complexity from 200 to 202. Hence, for a really large dataset, you can safely ignore the addition of log(n) as just a constant.

Hemanth
  • 5,035
  • 9
  • 41
  • 59