I have searched almost 5 books and may be 10 to 15 online resources to understand that concept of "one point at max in a square". Thank you, sir for explanation.
Why do we need to compare within 15 squares? Shouldn't it be 11 instead? There is no point comparing with squares which are 2 squares above the point. Can you please explain?
after dividing in to halfs ,we take the points at distance d and sort them according to y?But why according to y only and not according to x?if i sort by x again and i can give same argument that only at max 15 points will be accessed.Please clear this query.@13:25 ,the first line,why is has to be sorted by y?Will sot by x give wrong results?
I've had way too much free time during this quarantine. Here's the explanation of what you wanted with proof. Once you've found out the LD(minimum distance on the left side of the separator line L) and RD(...........right side of..........), you'd find delta which is the minimum of the aforementioned distances(DELTA=min(LD,RD)). Now, its time for finding the distance b/w the points lying on the EITHER SIDE of the line L. So you'd now construct the strip (of length 2*Delta) across L and search for the points lying within the strip and distanced < DELTA. We will now build a square(assume its either on the left or right side of the line L just for simplicity) with side=DELTA and see how many points fit in it conforming to our requirement that minD
@@studyonline3236 Are you sure all the 8 points in the two squares need to be calculated? I read somewhere you actually only need check 3 points, as long as the points are y coordinates non-decreasing ordered .
@@iJamesGuo can you share the source link? Btw there isn't much computational time difference between them as long as the computations are done in linear fashion. O(8n) ~=O(3n)~=O(n)
@@studyonline3236 Yes, I know it's linear. Just for the life of me can't figure why we only need to check 3. Your explanation helps, but I am still unclear of the magic number 3.
