Closest pair of points

To access the translated content:
1. The translated content of this course is available in regional languages. For details please visit nptel.ac.in/translation
The video course content can be accessed in the form of regional language text transcripts, books which can be accessed under downloads of each course, subtitles in the video and Video Text Track below the video.
Your feedback is highly appreciated. Kindly fill this form forms.gle/XFZhSnHsCLML2LXA6
2. Regional language subtitles available for this course
To watch the subtitles in regional languages:
1. Click on the lecture under Course Details.
2. Play the video.
3. Now click on the Settings icon and a list of features will display
4. From that select the option Subtitles/CC.
5. Now select the Language from the available languages to read the subtitle in the regional language.

[@malharjajoo7393]

Cant believe how a seemingly harmless question has such a complicated solution.

[@rakshitkathawate8838]

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.

[@vidhikumar1664]

Amazing explanation....explained something none of the other sources I went through did

[@dohyun0047]

i had to watch this multiple time to understand it was worthy thank you!!!!!

[@AciertoHombre]

Really good explanation

[@anujdhoot7804]

Lucid. Thank you so much :)

[@lupitasahu]

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?

[@xunweiye8067]

you are right

[@piyushbhatia234]

actually it should be only 7 points. if we are taking about 2d

[@rahulsharma5030]

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?

[@user-jl2tz3rq9f]

very good explanation!

[@keshavparihar2304]

Amazing explanation 💖💖

[@tsndiffopera]

15 is too optimistic. We can have a better lower bound of 7.

[@mxkep]

Very good!

[@hoomaneshghi253]

there is no need to check against 15 others, only 7 points of the other side is enough

[@TRPixel]

if it is 3d dimensinal , we need to check 15 ?

[@rakshitkathawate8838]

Yes that's good, small refinement in the problem.

[@mrsjain1419]

@@TRPixel look at the distance formula it is for 2 d not 3d

[@farhanhaikhan7307]

Are you sure?

[@sabujjana2860]

Nice

[@a3393962]

if some point falls on the split line, you will get wrong (you can't just split x by half-half, some of the point are on split line)

[@haniahania6941]

Can you please help me to write c++ source codes for different programs

[@hoomaneshghi253]

Thanks

[@elijaheinstein160]

Nice explanation! How to modify this algorithm when the x and y coordinates are not guaranteed to be distinct?

[@ras6746]

make them distinct first :)

[@nahidx]

I don't still understand "one point at max in a square". Does anyone has a better explaination?

[@studyonline3236]

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

[@iJamesGuo]

@@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 .

[@studyonline3236]

@@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)

[@iJamesGuo]

@@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.

[@toekneema]

Imagine having to solve this in an interview in nlogn

[@mistryhitenbharatkumar36]

😂😂 exit

[@PramodKumar-bu2uf]

anyone can share the code of this problem

[@PramodKumar-bu2uf]

in c++

[@b-33neelranka65]

hi

[@gauravmishra2888]

Yeah this tutorial is copied from tim

[@coolmagictrickwithapple7513]

Nah, you couldn't be more wrong..

[@brajeshmohanty2558]

Can you provide the channel name

[@LearnPythoninPashto]

we say to it ratalogist it means to memorize something but in practical quality is zero please don't waste time in such video