-3

The divide and conquer strategy for closest point problem sorts the points according to x coordinates so that the median could be found. But what does sorting the strip (strip array contains all the points which are at most d perpendicular distance apart from the median line where d is the minimum distance till now) according to the y coordinates serve any purpose? Is there something that cannot be done by the already x coordinate sorted array?

Link for reference

3
  • Look at 3.2: Thankfully, we can make another life saving observation at this point...
    – Kain0_0
    Mar 21, 2021 at 23:54
  • The link works in my device. Mar 22, 2021 at 3:33
  • @user12208242 you did nothing wrong with your URL. I'm seeing that Safari on Mac is Ok with the tilde "~" character as is, but somehow fails when it is properly re-encoded as "%7E". I tested this separately on a page on my Mac. But the current edit and your original seemed to work fine on Chrome from Windows. Also on Safari, a forward slash oddly shows up after ".html" before the anchor ".html/#anal" and that fails. So there are two things here that Safari on my Mac dislikes. I put in an edit that Safari seemed OK with but there's another edit instead that still fails for me. Mar 22, 2021 at 20:23

1 Answer 1

0

I think the answer is in the previous section 3.2 I've quoted below. I think this answers your immediate question.

However, since we sorted the points in the strip by their y-coordinates the process of merging our two subsets is not linear, but in fact takes O(nlogn) time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.