3 5 On log n Algorithm for Closest Pair II Advanced Optional 19 min

[@DaniloSouzaMoraes]

The algorithm is beautiful and the instructor is very good. Very clear explanation

[@jianxiang]

This thinking inspires me a lot.

[@code-with-carlos]

I was certainly confused with that seven points for-loop comparison in the previous video. This video made me realize of how cool this algorithm is. It is fairly interesting to see how the paradigm Divide and Conquer can drive to such algorithms.

[@__redacted__]

So the magic of all of this is in 1) using the delta derived from the distance between 2 points in Q or R to feed into the 3rd subroutine 2) recognizing the Pythagorean distance based on delta 3) respecting the split pair definition and 4) enumerating through the remaining possible pairings for a given point

[@nahjeesowah6022]

euclidean distance !=pythagorean distance

[@hidude1354]

@@nahjeesowah6022 aren't all euclidean distances in essence pythagorean distances? euclidean distances are just distances between two points calculated from pythagoras' theorem so I don't see why this point is brought up

[@nimishshah3971]

This is insane!

[@JoeBaloney]

Taking the base cases into consideration, we can have a max of 3 points on the left and a max of 3 points on the right, so the worst-case scenario for the ClosestSplitPair() function is to loop over 3X3=9 times to find the closest-split pair, which is a different number from the 8-square method. Where is the missing point? (no pun intended)

[@jiaruowang9492]

Thank you so much for the great great explanation. I would have dropped my algorithm class otherwise...

[@jonathanlee8162]

Can we use max 4 instead of 7? But that is if j iterates from after x bar.

[@jonathanlee8162]

But yup I understand that it’ll still be O(n) even if it’s 4

[@nahjeesowah6022]

now the real question is why 8 boxes, with this definition it could be variety of constants

[@soon931111]

I'm sorry, isn't the graph you drew called horizontal strip instead of vertical strip?

[@mcpickle91]

if you mean at 6:50, then I agree.

[@jonathanlee8162]

It’s the set of points from y = infinity to y= -infinity And between x bar + d and x bar - d. So yea it’s a vertical strip, but he didn’t draw the vertical lines

[@CLG111]

That was a very poor explanation. Didn't make a bit of sense. And people are paying Stanford dollars for this?